锐客网

  1. 首页 > it技术 > >

我写的|hdu5528 Count a * b

HDU我写的

Count a * b Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 262Accepted Submission(s): 132


Problem Description Marry likes to count the number of ways to choose two non-negative integersa andb less thanm to makea×b modm≠0.

Let's denotef(m) as the number of ways to choose two non-negative integersa andb less thanm to makea×b modm≠0.

She has calculated a lot off(m) for differentm, and now she is interested in another functiong(n)=∑m|nf(m). For example,g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26. She needs you to double check the answer.

我写的|hdu5528 Count a * b
文章图片


Give youn. Your task is to findg(n) modulo264.
Input The first line contains an integerT indicating the total number of test cases. Each test case is a line with a positive integern.

1≤T≤20000
1≤n≤109
Output For each test case, print one integers, representingg(n) modulo264.
Sample Input


2 6 514
Sample Output

26 328194
Source 2015ACM/ICPC亚洲区长春站-重现赛（感谢东北师大） 我写的|hdu5528 Count a * b
文章图片

#include const int maxn=100001; using namespace std; bool bb[maxn]; int prim[maxn],tot,v[maxn],s[maxn],t[maxn],n; void prepare(){ bb[1]=1; v[1]=1; t[1]=1; for(int i=2; i<=maxn; i++){ if(!bb[i]){ prim[++tot]=i; v[i]=2*i-1; s[i]=1; t[i]=i; } for(int j=1; j<=tot&&prim[j]*i1){ ans1*=(1LLU*n*n+1); ans2*=2*n; } //cout<



    推荐阅读


    上一篇：Spring|SpringBoot学习（五）--SpringBoot集成redis缓存及redis客户端

    下一篇：ACM_位运算|位运算的简单总结