牛客练习赛-反演、差分

题目链接

枚举因子如果,那么在这个区间内都有贡献，即这个区间都加上这个贡献，显然用差分解决。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in","r",stdin);
#define OUT freopen("out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int phi[N];
int cnt=0,pri[N];
bool vis[N];
ll f[N];
void MOD(ll &x){
    if(x<0)x+=mod;
    if(x>=mod) x%=mod;
}
void pre(){
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*pri[j]<N;j++){
            vis[i*pri[j]]=true;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
    for(int d=1;d<N;d++){
        ll s=0;
        for(int n=d;n<N;n+=d){
            MOD(s+=phi[n]);
            int l=n,r=n+d;
            ll x=s*s%mod*phi[d]%mod;
            MOD(f[l]+=x);
            if(r>=N)continue;
            MOD(f[r]-=x);
        }
    }
    for(int i=1;i<N;i++)MOD(f[i]+=f[i-1]);
}
int main(){
    pre();
    int n;cin>>n;
    for(int i=1;i<=n;i++)pr("%lld\n",f[i]);
}