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.
文章图片
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亚洲区长春站-重现赛(感谢东北师大)
文章图片
#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<
推荐阅读
- hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)
- HDU|HDU 1576 A/B(拓展欧几里得,模板题)
- 比赛题解|2020 杭电多校9 1007 Game (平衡树)
- hdu|HDU 6133 Army Formations 树状数组 + 启发式合并
- HDU|HDU 5528 狄利克雷卷积
- hdu|【hdu 5354】Bipartite Graph【分治 并查集】
- online|hdu4115Eliminate the Conflict
- online|hdu5955Guessing the Dice Roll
- online|hdu1816Get Luffy Out *
- online|hdu3622Bomb Game