题目链接

题解

考虑枚举 $i$ ，定义

g(n,m)=\sum_{i=1}^m \varphi(in)

假设

n=\prod_{k}p_k^{a_k}

令

n&#x27;=\prod_{k}p_k\\ r=\prod_{k}p_k^{a_k-1}

那么

g(n,m)=r\sum_{i=1}^m \varphi(in)

反演得到

g(n,m)=r\sum_{d|n&#x27;}\varphi(\frac{n&#x27;}{d})g(d,\lfloor\frac{m}{d}\rfloor)

可以递归求解。

事实上，由于每次递归 $d ∣ n^{'}$ ，因此只需要最开始提出 $r$ ，后面的 $r$ 必定 $= 1$ 。

代码

#include #include 
    
     int read(){
     int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
         if(ch=='-')        {
             f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
         x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=1000000;const int maxm=100000;const int mod=1000000007;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],phi[maxn+10],last[maxm+10],sum[maxn+10];int getprime(){
     p[1]=phi[1]=mu[1]=1;  for(int i=2; i<=maxn; ++i)    {
         if(!p[i])        {
             prime[++cnt]=i;          phi[i]=i-1;          mu[i]=-1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
             int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                 mu[x]=0;              phi[x]=phi[i]*prime[j];              break;            }          mu[x]=-mu[i];          phi[x]=phi[i]*(prime[j]-1);        }    }  for(int i=1; i<=maxm; ++i)    {
         if(mu[i])        {
             for(int j=i; j<=maxm; j+=i)            {
                 last[j]=i;            }        }    }  for(int i=1; i<=maxn; ++i)    {
         sum[i]=sum[i-1]+phi[i];      if(sum[i]>=mod)        {
             sum[i]-=mod;        }    }  return 0;}std::map
     
       mp;int getphi(int n){
     if(n<=maxn)    {
         return sum[n];    }  if(mp.count(n))    {
         return mp[n];    }  int res=(1ll*n*(n+1)/2)%mod;  for(int l=2,r; l<=n; l=r+1)    {
         r=n/(n/l);      res=(res-1ll*(r-l+1)*getphi(n/l))%mod;    }  if(res<0)    {
         res+=mod;    }  return mp[n]=res;}struct data{
     int n,m;  data(int _n=0,int _m=0):n(_n),m(_m){
   }  bool operator <(const data &oth) const  {
       return (n==oth.n)?(m
      
       
         mf;int F(int n,int m){
     if(m==0)    {
         return 0;    }  if(n==1)    {
         return getphi(m);    }  data d(n,m);  if(mf.count(d))    {
         return mf[d];    }  int ans=0;  for(int i=1; i*i<=n; ++i)    {
         if(n%i!=0)        {
             continue;        }      ans=(ans+1ll*phi[n/i]*F(i,m/i))%mod;      if(i*i!=n)        {
             ans=(ans+1ll*phi[i]*F(n/i,m/(n/i)))%mod;        }    }  return mf[d]=ans;}int n,m;int main(){
     getprime();  n=read();  m=read();  int ans=0;  for(int i=1; i<=n; ++i)    {
         ans=(ans+1ll*(i/last[i])*F(last[i],m))%mod;    }  printf("%d\n",ans);  return 0;}

转载地址：https://blog.csdn.net/wang3312362136/article/details/86238825 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：BZOJ 4815 [Cqoi2017]小Q的表格

下一篇：BZOJ 4652 [Noi2016]循环之美

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题解

代码

发表评论

最新留言

关于作者

推荐文章