https://nanti.jisuanke.com/t/31448
题意
已知a序列，给你一个n和m求小于n与m互质的数作为a序列的下标的和
分析
打表发现ai=i*(i+1)。
易得前n项和为 Sn=n*(n+1)(2*n+1)/6+n*(n+1)/2;我们直接求与m互质的数较难，所以我们可以换个思路，求与 m不互质的数，那么与m不互质的数，是取m的素因子的乘积（因为根据唯一分解定理，任意个数都可看作的素数积），那么我们将m分解质因数，通过容斥定理，就可以得道与m不互质的数，总和sum减去这些数对应的a的和就是答案了。
容斥原理的具体如下：
区间中与i不互质的个数 = （区间中i的每个质因数的倍数个数）-（区间中i的每两个质因数乘积的倍数）+（区间中i的每3个质因数的成绩的倍数个数）-（区间中i的每4个质因数的乘积）+...
比如存在一个素因子是k，那么需要求下标为k，2k，3k，4k……的a的和，即求
通项的求和，为
，项数为n/k。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + ;
const int mod = 1e9 + ;
ll inv6=;
ll inv2=;
ll a[maxn];
ll cal(ll n,ll x){
n/=x;
return (n*(n+)%mod*(*n+)%mod*inv6%mod*x%mod*x%mod+n*(n+)%mod*inv2%mod*x%mod)%mod;
}
int main(){
ll n,m;
while(~scanf("%lld%lld",&n,&m)){
ll tot = cal(n,);
int cnt=;
for(ll i=;i*i<=m;i++){
if(m%i==){
a[cnt++]=i;
while(m%i==) m/=i;
}
}
if(m!=) a[cnt++]=m;
ll res=;
for(int i=;i<(<<cnt);i++){
ll tmp=;
for(int j=;j<cnt;j++){
if((<<j)&i){
tmp=tmp*a[j]%mod;
}
}
tmp=cal(n,tmp);
if(__builtin_popcount(i)&) res=(res+tmp)%mod;
else res=(res-tmp+mod)%mod;
}
printf("%lld\n",(tot-res+mod)%mod);
}
return ;
}