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
2
6
Sample Output
3
15
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)]
|
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#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：下一篇 »