51Nod1190 最小公倍数之和 V2

题目看这里

繁衍反演真好玩

来看看这个题的式子

求Σlcm(i,b) (a<=i<=b)

首先不难发现以下这样的变换

让后做一下差分就得到答案，注意这题比较卡时间，需要比较好的优化

#pragma GCC opitmize("O3") #pragma G++ opitmize("O3") #include<stdio.h> #include<string.h> #include<algorithm> #define N 40010 #define LL long long #define M 1000000007 using namespace std; bool vis[N]; int t,w[N],n; inline LL F(LL i,int m){ return (i+i*m)*m>>1; } inline void rd(int& x){ char c=getchar(); x=0; for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48); } inline void out(int x){ char c[10]; int j=0; for(;x;x/=10) c[++j]=x%10; for(;j;--j) putchar(c[j]^48); putchar('\n'); } int init(){
    n=40000; for(int i=2;i<=n;++i){ if(!vis[i]) w[++t]=i; for(int j=1,k;j<=t&&(k=i*w[j])<=n;++j){
            vis[k]=1; if(i%w[j]==0) break; } } } int p[210],k[210],cnt; struct D{ int d,mu; } d[10000]; inline bool c1(D x,D y){ return x.d<y.d; } inline void dfs(int i,int S,int m){ if(i>t){ d[++cnt]=(D){S,m}; return; }
    dfs(i+1,S,m);
    dfs(i+1,S*=p[i],-m); for(int j=2;j<=k[i];++j)
        dfs(i+1,S*=p[i],0); } inline LL cal(int m,int n){ int x=n; t=cnt=0; LL ans=0; for(int i=1;w[i]*w[i]<=n;++i) if(x%w[i]==0){
            p[++t]=w[i]; k[t]=0; for(;x%w[i]==0;x/=w[i]) ++k[t]; } if(x>1) p[++t]=x,k[t]=1;
    dfs(1,1,1); LL k;
    sort(d+1,d+1+cnt,c1); for(int i=1;i<=cnt;++i) if(d[i].mu) for(int j=1;(k=(LL)d[i].d*d[j].d)<=n&&j<=cnt;++j) if(n%k==0)
            ans=(ans+(d[i].mu>0?(F(d[i].d,n/k)-F(d[i].d,m/k)):(F(d[i].d,m/k)-F(d[i].d,n/k))))%M; return (ans+M)%M; } int main(){
    init(); int T; rd(T); for(int n,m;T--;out(cal(m-1,n)*n%M)) rd(m),rd(n); }