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

时间:2022-06-19 14:06:09

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