HDU 5528【2015长春现场赛 B】 Count a * b 数论

http://acm.hdu.edu.cn/showproblem.php?pid=5528
题意读入m，求

∑n|m∑1≤i≤n1≤j≤n[n?i×j]
题解 【HDU 5528【2015长春现场赛 B】 Count a * b】
∑n|m∑1≤i≤n1≤j≤n[n?i×j]=∑n|m∑1≤i≤n(n?gcd(n,i))=∑n|m(n2?∑1≤i≤ngcd(n,i))=∑n|m(n2?∑d|n(?(nd)×d))=∑n|mn2?∑n|m∑d|n(?(nd)×d))
下面化简 ∑n|m∑d|n(?(nd)×d))=∑d|n∑n|m(?(nd)×d))令n=ed，则ed|m?e|md=∑d|m∑e|md(?(e)×d))=∑d|md∑e|mde
由 ∑d|n?(d)=n，故
=∑d|md×md=∑d|mm=∑n|mm
故原式
=∑n|mn2?∑n|mm=∑n|m(n2?m)

注意：此题求约数不能用 n??√ 的写法

code

#include #include #include typedef unsigned long long LL; const int maxp = 50010; const int maxn = 100010; int n; int prime[maxp], prime_N; bool isprime[maxn]; void gen(int n) { prime_N = 0; memset(isprime, 1, sizeof isprime); isprime[0] = isprime[1] = 0; for (int i = 2; i < n; ++ i) { if (isprime[i]) prime[prime_N ++] = i; for (int j = 0, k; j < prime_N && (k = i*prime[j]) < n; ++ j) { isprime[k] = 0; if (!(i%prime[j])) break; } } } int pri[maxp], pri_num[maxp], pri_N; void get_pri(int n) { pri_N = 0; for (int i = 0, p; (p = prime[i])*p <= n; ++ i) if (n%p == 0) { pri[pri_N] = p; pri_num[pri_N] = 0; while (n%p == 0) { n /= p; ++ pri_num[pri_N]; } ++ pri_N; } if (n > 1) { pri[pri_N] = n; pri_num[pri_N] = 1; ++ pri_N; } } LL res; void dfs_divisor(int d, int div) { if (d == pri_N) { res = res + ((LL)div*div - n); return; } for (int i = 0; i <= pri_num[d]; ++ i) { dfs_divisor(d+1, div); div = div * pri[d]; } }void solve() { scanf("%d", &n); get_pri(n); res = 0; dfs_divisor(0, 1); printf("%I64u\n", res); }int main() { //freopen("1002.in", "r", stdin); gen(100000); int kase; scanf("%d", &kase); while (kase --) solve(); //for(; ; ); return 0; }