锐客网

  1. 首页 > it技术 > >

HDU 5528 Count a * b(数论)

HDOJ

k(n)=n*n-f(n)
可以知道对于一个k(p1^a1*p2^a2....pn^a2)=k(k1^a1)*....*k(kn^an)
然后又对于k(p^a)=(a+1)*(p^a)-k*(p^a-1)
那么对于g(n)=约数平方和+素数的h的和的乘机



#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define sp system("pause")typedef long long ll; typedef unsigned long longull; typedef pair pii; typedef pair piii; const int MAXN = 32000 + 500; int prime[MAXN + 1]; vectormyp; void getprime() { memset(prime, 0, sizeof prime); for (int i = 2; i <= MAXN; i++) { if (!prime[i])prime[++prime[0]] = i, myp.push_back(i); for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++) { prime[prime[j] * i] = 1; if (i%prime[j] == 0)break; } } }vector【HDU 5528 Count a * b(数论)】fac; void getfac(int x) { for (int i = 0; i < myp.size(); i++) { int cot = 0; while (x%myp[i] == 0)x /= myp[i], cot++; if (cot)fac.push_back(pii(myp[i], cot)); } if (x>1)fac.push_back(pii(x, 1)); }int main() { int T; getprime(); cin >> T; while (T--) { int x; scanf("%d", &x); ull tx = x; fac.clear(); getfac(x); ull all = 0; //for (ull i = 1; i*i <= tx; i++) // if(tx%i==0)all += i*i,all+=(tx/i)*(tx/i); ull now = 1; for (int i = 0; i < fac.size(); i++) { ull diall = 1; ull nowplus = fac[i].first; ull nowpow = 0; ull cotall = 0; for (int j = 1; j <= fac[i].second; j++) { diall += (ull)(j + 1)*(nowplus)-((ull)j*nowplus / fac[i].first); nowpow = nowpow + nowplus*nowplus; nowplus =nowplus*(ull) fac[i].first; } all = all*(nowpow + 1); all = all + nowpow; now *= diall; } all++; printf("%llu\n", all - now); } }//int main() //{ // int cot[200] = { 0 }; // for (int i = 1; i <= 40; i++) // { //for (int j = 1; j <= i; j++) //{ //for (int k = 1; k <= i; k++) //{ //if ((k*j) % i == 0)cot[i]++; //} //} // } // for (int i = 1; i <= 40; i++) //cout << i << " " << cot[i] << endl; // sp; //}



    推荐阅读


    上一篇：LeetCode 28. Implement strStr()（字符串匹配问题）

    下一篇：LeetCode 35. Search Insert Position（查找插入位置）