星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

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

posted on 2018-04-19 23:40:31 | under 题解 |

被YMY先看到了这道题不开心。

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

关于推式子这方面的东西仍然被楼下抢了而且大家套路怎么都一模一样,我这里只是说一下那个 $N_k$ 应该是没有必要算的,因为你只会利用到它下标为质数的部分。以及一份在数学题里面基本上没有什么卵用的参考代码
然后因为没卡常数并且全程 $\rm long\ long$ 的原因速度比楼下低到不知道哪里去了。
$\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;
}