当前位置:首页 >> 学科竞赛 >>

bzoj4407


#include<cstdio> #include<algorithm> #define?MO?1000000007 #define?XMAX?5000100 #define?ll?long?long?int using?namespace?std; int?szm[XMAX+100]; int?szp[XMAX+100]; int?szd[XMAX+10

0]; int?szf[XMAX+100]; int?szs[XMAX+100]; int?totp; int?numt; int?k; int?kmi(int?a,int?b) { int?ans; for(ans=1;b!=0;b>>=1) { if(b&1) ans=(ll)ans*a%MO; a=(ll)a*a%MO; } return?ans; } void?init() { int?to; int?f1; int?f2; szf[1]=1; szs[1]=1; for(f1=2;f1<=XMAX;f1++) { if(szm[f1]==0) { szm[f1]=f1; szd[f1]=f1; szp[++totp]=f1; szf[f1]=(kmi(f1,k)?1+MO)%MO; } else if(szd[f1]==f1) szf[f1]=(kmi(f1,k)?kmi(f1/szm[f1],k)+MO)%MO; else szf[f1]=(ll)szf[szd[f1]]*szf[f1/szd[f1]]%MO; szs[f1]=(szs[f1?1]+szf[f1])%MO; for(f2=1;(f2<=totp)&&(szp[f2]<=szm[f1])&&((ll)szp[f2]*f1<=XMAX);f2++) { to=szp[f2]*f1; szm[to]=szp[f2]; if(szp[f2]==szm[f1]) szd[to]=szd[f1]*szp[f2]; else szd[to]=szp[f2]; } }

return; } int?main() { int?ans; int?z1; int?z2; int?f0; int?f1; int?f2; scanf("%d%d",&numt,&k); init(); for(f0=1;f0<=numt;f0++) { ans=0; scanf("%d%d",&z1,&z2); if(z1>z2) swap(z1,z2); for(f1=1;f1<=z1;f1=f2+1) { f2=min(z1/(z1/f1),z2/(z2/f1)); ans=(ans+(ll)(szs[f2]?szs[f1?1]+MO)%MO*(z1/f1)%MO*(z2/f1)%MO)%MO; } printf("%d\n",ans); } return?0; }


相关文章:
更多相关标签: