锐客网

  1. 首页 > it技术 > >

HDU5528 Count a b(欧拉函数&数的分解)

数论

HDU5528 Count a * b(欧拉函数&数的分解) 题目大意 【HDU5528 Count a b(欧拉函数&数的分解)】设 f ( n ) f(n) f(n)为小于n的a，b使得有 a × bm o dn = ? 0 a\times b\ mod \ n =\not 0 a×b mod n=??0的a，b的组数。现定义 g ( n ) = ∑ d ∣ n f ( d ) g(n)=\sum_{d|n}f(d) g(n)=∑d∣n?f(d),现给出n求g(n)
解题思路 f ( n ) = n ? n ? ∑ i = 0 n ? 1 ∑ j = 0 n ? 1 n ∣ ( i ? j ) = n ? n ? ∑ i = 0 n ? 1 ∑ j = 0 n ? 1 n g c d ( n , i ) ∣ ( i g c d ( n , i ) ? j ) = n ? n ? ∑ i = 0 n ? 1 ∑ j = 0 n ? 1 n g c d ( n , i ) ∣ j = n ? n ? ∑ i = 0 n ? 1 g c d ( n , i ) f(n)=n*n-\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}n|(i*j)\\ =n*n-\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}{n\over gcd(n,i)}|({i\over gcd(n,i)}*j)\\ =n*n-\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}{n\over gcd(n,i)}|j\\ =n*n-\sum_{i=0}^{n-1}gcd(n,i) f(n)=n?n?i=0∑n?1?j=0∑n?1?n∣(i?j)=n?n?i=0∑n?1?j=0∑n?1?gcd(n,i)n?∣(gcd(n,i)i??j)=n?n?i=0∑n?1?j=0∑n?1?gcd(n,i)n?∣j=n?n?i=0∑n?1?gcd(n,i)
此时需要用到一个常用套路 ∑ i = 1 n g c d ( n , i ) = ∑ d ∣ n d φ ( n d ) \sum_{i=1}^{n}gcd(n,i)=\sum_{d|n}d\varphi({n\over d}) ∑i=1n?gcd(n,i)=∑d∣n?dφ(dn?)
那么原式就可以化成
= n ? n ? ∑ d ∣ n d φ ( n d ) =n*n-\sum_{d|n}d\varphi({n\over d}) =n?n?d∣n∑?dφ(dn?)
将 f ( n ) f(n) f(n)带入
g ( n ) = ∑ d ∣ n d 2 ? ∑ d ∣ n ∑ i ∣ d i φ ( d i ) = ∑ d ∣ n d 2 ? ∑ i ∣ n i ∑ i ∣ d & d ∣ n φ ( d i ) = ∑ d ∣ n d 2 ? ∑ i ∣ n i ∑ k ∣ n i φ ( k ) g(n)=\sum_{d|n}d^2-\sum_{d|n}\sum_{i|d}i\varphi({d\over i})\\ =\sum_{d|n}d^2-\sum_{i|n}i\sum_{i|d\& d|n}\varphi({d\over i})\\ =\sum_{d|n}d^2-\sum_{i|n}i\sum_{k|{n\over i}}\varphi(k)\\ g(n)=d∣n∑?d2?d∣n∑?i∣d∑?iφ(id?)=d∣n∑?d2?i∣n∑?ii∣d&d∣n∑?φ(id?)=d∣n∑?d2?i∣n∑?ik∣in?∑?φ(k)
此时需要用到欧拉函数的一个性质
∑ d ∣ n φ ( d ) = n \sum_{d|n}\varphi(d)=n d∣n∑?φ(d)=n
原式就可以换成
= ∑ d ∣ n d 2 ? ∑ i ∣ n i n i = ∑ d ∣ n d 2 ? ∑ i ∣ n n =\sum_{d|n}d^2-\sum_{i|n}i{n\over i}\\ =\sum_{d|n}d^2-\sum_{i|n}n =d∣n∑?d2?i∣n∑?iin?=d∣n∑?d2?i∣n∑?n
接下来分解因数即可。本题时限卡得比较严格，分解时需要先处理出质数，再做质因数分解
AC代码

#include using namespace std; typedef unsigned long long ULL; typedef pair pii; const int maxn=sqrt(1e9)+1; int tot=0; pii pri[100]; ULL ans=0; int cnt=0; int tots=0; int prime[maxn]; bool p[maxn]; void init() { memset(p,1,sizeof(p)); for(int i=2; i

    推荐阅读


    上一篇：Android|Android Studio 解决导入其他项目慢或者卡死的问题

    下一篇：【Eureka篇三】Eureka如何管理服务调用（6）