BZOJ 2705: [SDOI2012]Longge的问题( 数论 )

T了一版....是因为我找质因数的姿势不对...

考虑n的每个因数对答案的贡献. 答案就是 ∑ d * phi(n / d) (d | n) 直接枚举n的因数然后求phi就行了.

但是我们可以做的更好.

注意到h(n) = ∑ d * phi(n / d) (d | n) 是狄利克雷卷积的形式, 而且f(x) = x 和 f(x) = phi(x) 都是积性函数, 所以答案h(x) 也是积性函数.

所以h(x) = Π h(p^k) (p 是 x 的质因数)

由phi(p^k) = p^k - p^(k-1), h(p^k) 很好求. 化简一下得到 h(p^k) = (k + 1) * p^k - k * p^(k - 1)

--------------------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {

ll n, ans = 1, cnt , h;

cin >> n;

for(ll p = 2; p * p <= n; p++) if(n % p == 0) {

cnt = 0; h = 1;

for(; n % p == 0; n /= p, h *= p) cnt++;

ans *= (cnt + 1) * h - cnt * h / p;

}

if(n != 1) ans *= 2 * n - 1;

cout << ans << "\n";

return 0;

}

--------------------------------------------------------------------------------------

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1508  Solved: 937
[Submit][Status][Discuss]

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据，0<N<=2^16。

对于100%的数据，0<N<=2^32。

Source

round1 day1