题解 P4449 【于神之怒加强版】

~~被YMY先看到了这道题不开心。~~ ### 蒟蒻怒交BZOJRE代码，然后发现自己以前写数论题都打的啥~~还交了7遍~~...... 关于推式子这方面的东西仍然被楼下抢了~~而且大家套路怎么都一模一样~~，我这里只是说一下那个$N_k$应该是没有必要算的，因为你只会利用到它下标为质数的部分。~~以及一份在数学题里面基本上没有什么卵用的参考代码~~ ~~然后因为没卡常数并且全程$\rm long\ long$的原因速度比楼下低到不知道哪里去了。~~ $\rm int+1ll\vert(long\ long)$这种操作还是蛮好用的，尤其是在比赛的评测环境下可以跑得很快。大家可以学习一个~~虽然我没写~~。 ```cpp #include<cstdio> #define neko 5500010 #define chkmin(a,b) ((a)<(b)?(a):(b)) #define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i))) typedef long long ll; static ll n,m,k,ans,mod=1e9+7; static int cas; typedef long long arr[neko]; static arr isnprime,prime,F,sumF,Pow; template<typename T> void swap(T &a,T &b){T t=a;a=b,b=t;} static ll slowpow(ll m,ll n) { ll b=1; for(;n;n>>=1,m=m*m%mod)if(n&1)b=b*m%mod; return b; } inline void sieve() { F[1]=1,Pow[1]=1; f(i,2,5000010) { if(!isnprime[i])prime[++prime[0]]=i,F[i]=slowpow(i,k)-1,Pow[i]=F[i]+1; for(register int j=1;j<=prime[0]&&prime[j]*i<=5000010;j++) { isnprime[i*prime[j]]=1; // Pow[i*prime[j]]=Pow[i]*Pow[prime[j]]%mod; if(i%prime[j]==0){F[i*prime[j]]=F[i]*Pow[prime[j]]%mod;break;} F[i*prime[j]]=F[i]*F[prime[j]]%mod; } }f(i,1,5000010)sumF[i]=sumF[i-1]+F[i],sumF[i]%=mod; } int main() { int j; scanf("%d%lld",&cas,&k); sieve(); while(cas--) { scanf("%lld%lld",&n,&m); ans=0; if(n>m)swap(n,m); for(register int i=1;i<=n;i=j+1) { j=chkmin(n/(n/i),m/(m/i)); ans=(ans+(n/i)*(m/i)%mod*(sumF[j]-sumF[i-1])%mod)%mod; }printf("%lld\n",(ans+mod)%mod); }return 0; } ```