题目链接
题意：定义数列an为
首先，通过打表或者递推可以得到an的通项为n*(n+1)。然后，如果是求1到n中与m互质的数的个数，我们可以较容易的通过容斥原理得到与m不互质的数的个数，然后减去即可。那么，如何求出题目要求的呢？
解题前须知：
，
i*(i+1)=i^2+i，所以有
先给一道题的链接：hdu 4407 Sum。这道题要求1到n中与m互质的数的和，虽然数据范围小一点，而且还有修改操作，但是可以发现要求的和与这道题是类似的。
假设对于无修改操作的hdu4407：将m分解质因数，然后枚举m的所有不含有重复质因子的因数，计算出每种因子的倍数的和，通过容斥计算出所有和m不互质的数的和，最后用n*(n+1)/2减去该值即可。可知对于每一个因子p，它的倍数的和为，用等差数列求和公式即可O(1)求出解，因此总的复杂度是容斥带来的O(2^t)（假设t个质因子）。
而对于本题，不过是将与m互质的i的和变为了与m互质的i的i*(i+1)=i^2+i的和，那么同样计算出每种因子的倍数的i*(i+1)的和，通过容斥计算出所有与m不互质的数的i*(i+1)的和，最后用减去该值即可。可知对于每一个因子p，它的倍数的i*(i+1)的和不方便直接通过公式计算，但是拆成i^2和i的和分别计算很方便，分别为和。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define clr( x , y ) memset(x,y,sizeof(x))
#define cls( x ) memset(x,0,sizeof(x))
#define mp make_pair
#define pb push_back
#define ll long long
const int mod=1e9+7;
map<int , int>v ;
vector<int>fac ;
int qpow(int a,int b){int res=1;while(b){if(b&1) res=res*1ll*a%mod;b>>=1;a=a*1ll*a%mod;}return res;
}
int inv;
ll cal( int l , int r , int val ){int tt=r/val;ll a1=(l%val==0)?l:(val-l%val)+l;ll an=r-r%val;ll res=((ll)(a1+an)*(ll)tt/2)%mod; // 等比数列求和公式res=(res+val*1ll*val%mod*tt%mod*(tt+1)%mod*(2*tt+1)%mod*inv%mod)%mod;//求倍数的i^2的和return res ;
}ll work( int l , int r , int p ){fac.clear();for( int i = 2 ; i * i <= p ; i++ ){//暴力对m分解质因数if( p % i == 0 ){fac.pb( i ) ;while( p % i == 0 ) p /= i ;}}if( p > 1 ) fac.pb( p ) ;int s = fac.size() ;ll res = 0 ;for( int i = 1 ; i < ( 1 << s ) ; i++ ){//枚举因子int bits = 0 ;ll val = 1 ;for( ll j = 0 ; j < s ; j++ ){if( i & ( 1 << j ) ){bits++ ;val *= fac[j] ;}}ll tmp = cal( l , r , val ) ;if( bits & 1 ) // 容斥原理res += tmp ;elseres -= tmp ;}ll sum=(ll)(l+r)*(ll)(r-l+1)/2%mod;sum=(sum+r*1ll*(r+1)%mod*(2*r+1)%mod*inv%mod)%mod;//sum为总和，减去不互质的和res=(sum-res)%mod;return res ;
}
ll solve( int l , int r , int p ){ll res = work( l , r , p ) ;return res ;
}
int n,m;
int main(){inv=qpow(6,mod-2);//处理出6的逆元while(~scanf("%d %d",&n,&m)){ll ans=solve(1,n,m);printf("%lld\n",(ans%mod+mod)%mod);}return 0;
}