链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501
求一个数n的所有小于它并且与它不互质的数的和。
打算复习一波欧拉函数的,结果这题发现可以容斥。
我们知道如果一个数$n$含有因数$x$,那么$x$的倍数都和$n$不互质,且质因数至少为$x$。
我们可以知道,对于任意小于$n$的因数$x$,对本题的贡献为$x+2x+3x+…+kx=frac{k(k+1)}{2}x$,其中$k$为$n$对$x$的倍数。
于是直接对$n$分解因数,再容斥。
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
using namespace std ;typedef long long LL;const LL mod = 1e9 +7 ;LL n; LL (LL a, LL b, LL &x, LL &y) { if (b == 0 ) { x = 1 ; y = 0 ; return a; } else { LL ret = exgcd(b, a%b, x, y); LL tmp = x; x = y; y = tmp - a / b * y; return ret; } } LL inv (LL a) { LL x, y; exgcd(a, mod, x, y); return (x % mod + mod) % mod; } signed main () { while (~scanf ("%lld" ,&n) && n) { LL t = n; vector <LL> p; for (LL i = 2 ; i * i <= n; i++) { if (n % i == 0 ) p.push_back(i); while (n % i == 0 ) n /= i; } if (n > 1 ) p.push_back(n); int nn = 1 << p.size(); LL ret = 0 ; for (int i = 1 ; i < nn; i++) { LL tmp = 1 ; for (int j = 0 ; j < p.size(); j++) { if (i & (1 << j)) { tmp *= p[j]; } } LL cnt = t / tmp; tmp = cnt * (cnt - 1 ) % mod * inv(2 ) % mod * tmp % mod; if (__builtin_popcount(i) & 1 ) { ret += tmp; ret %= mod; } else { ret -= tmp; ret += mod; ret %= mod; } } printf ("%lldn" , ret); } return 0 ; }
再来考虑欧拉函数,知道一个定理:小于$n$的数,且与$n$互质的数的和为: $$ frac{phi(n)×n}{2} $$ 然而小于$n$的数的和为$frac{n(n-1)}{2}$,于是我们一减: $$ frac{n(n-1-phi(n))}{2} $$
1 2 3 4 5 6 7 8 9 10 11 12 13 14
signed main () { while (~scanf ("%lld" ,&n) && n) { LL ret = n, t = n; for (LL i = 2 ; i * i <= n; i++) { if (n % i == 0 ) ret = ret / i * (i-1 ); while (n % i == 0 ) n /= i; } if (n > 1 ) ret = ret / n * (n-1 ); LL p = t * (t - 1 - ret) / 2 ; cout << p % mod << endl ; } return 0 ; }
近期评论