2018-04-19 23:40:31

### 蒟蒻怒交BZOJRE代码，然后发现自己以前写数论题都打的啥还交了7遍......

$\rm int+1ll\vert(long\ long)$ 这种操作还是蛮好用的，尤其是在比赛的评测环境下可以跑得很快。大家可以学习一个虽然我没写

#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;
}
• star
首页