poj2480

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

15 9月 2015

Longge's problem

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

Input

Input contain several test case.
A number N per line.

Output

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input

Sample Output

Source

POJ Contest,Author:Mathematica@ZSU

题目类型：素因子分解+积性函数

算法分析：由于n比较大，直接使用sigma (i * Euler(n/i)), i |n会TLE，此时应该进行进一步的推导。简单来说就是可以将积性函数f(x)=x和g(x)=Euler(x)进行一次狄利克雷卷积。而积性函数的狄利克雷卷积仍旧是积性函数。记卷积的结果是G(n)，由积性函数的性质可得：G(n) = G(p1 ^ a1) * G(p2 ^ a2) * G(p3 ^ a3) * ……G(pn ^ an)。将公式进行化简最后可得G(n) =

[(a1+1) * p1 ^ a1 - a1 * p1 ^ (a1-1)] * [(a2+1) * p2 ^ a2 - a2 * p2 ^ (a2-1)] * [(a3+1) * p3 ^ a3 – a3 * p3 ^ (a3-1)] * …… * [(an+1) * pn ^ an - an * pn ^ (an-1)]

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 50000 + 66;

int main()
{
//	ifstream cin("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    long long n;
    while (cin>>n)
	{
        long long res = n;
        for (long long i = 2; i * i <= n; i++)
		{
            if(n % i == 0)
			{
                long long p = i, cnt = 0;
                while (n % p == 0)
				{
                    cnt++;
                    n /= p;
				}

				res += res * cnt * (p - 1) / p;
			}
		}

		if (n != 1)
			res = res * (n * 2 - 1) / n;

		printf("%lld\n", res);
	}
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 50000 + 66;

int main()

{

// ifstream cin("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

long long n;

while (cin>>n)

{

long long res = n;

for (long long i = 2; i * i <= n; i++)

{

if(n % i == 0)

{

long long p = i, cnt = 0;

while (n % p == 0)

{

cnt++;

n /= p;

}

res += res * cnt * (p - 1) / p;

}

if (n != 1)

res = res * (n * 2 - 1) / n;

printf("%lld\n", res);

}

return 0;

}

poj2479

poj2513

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

poj2480

分类目录

标签云

书签

近期评论