HDU 4944 FSF’s game

數論

恩，好久沒有來弄數學了><

是說有簡便的方法啦@@ 只是我想賴皮一下><

f(gx, gy) = xy sigma i (i|g)

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define N 500010
using namespace std;
typedef unsigned long long int int64;
//typedef unsigned int uint;
vector<int64> _div[N+1];
vector<int64> _drc[N+1];
bool sieve[N+1];
int64 g[N+1];
int64 sf[N+1];
int64 r[N+1];
int64 p32 = 1;
inline void assertRE(bool t){
if(t == false)
printf("%d", 1/0);
return;
}
int main()
{
for(int lx = 1;lx <= 32;lx++) p32=p32*2;
memset(sieve, false, sizeof(sieve));
for(int lx = 2;lx <= N;lx++){
if(sieve[lx] == false){
for(int ly = 2;ly*lx <= N;ly++)
sieve[lx*ly] = true;
for(int ly = 1;ly*lx <= N;ly++)
_drc[ly*lx].push_back((int64)lx);
}
}
r[1] = 1, r[0] = 0;
for(int lx = 2;lx <= N;lx++){
r[lx] = (int64)lx;
for(int ly = 0;ly < _drc[lx].size();ly++){
int64 pp = _drc[lx][ly];
r[lx]=(r[lx]/pp*(pp-1))%p32;
}
//assertRE(r[lx]*lx%2==0);
r[lx] = (r[lx]*lx/2)%p32;
}

for(int lx = 1;lx <= N;lx++)
for(int ly = 1;ly*lx <= N;ly++)
_div[lx*ly].push_back((int64)lx);

for(int lx = 1;lx <= N;lx++){
g[lx] = 0;
for(int ly = 0;ly < _div[lx].size();ly++)
g[lx] = (g[lx] + _div[lx][ly])%p32;
}

sf[0] = 0;
for(int lx = 1;lx <= N;lx++){
int64 ff = 0;
for(int ly = 0;ly < _div[lx].size();ly++){
int64 val = _div[lx][ly];
int64 ival = lx/val;
ff = (ff + (lx*((g[val]*r[ival])%p32))%p32)%p32;
}
sf[lx] = (sf[lx-1]+ff)%p32;
}
int T;scanf("%d", &T);
for(int lt = 1; lt<=T ; lt++){
int q;scanf("%d", &q);
printf("Case #%d: %I64u\n", lt, sf[q]);
}

return 0;
}