ACM-ICPC 2018 沈阳赛区网络预赛 G.Spare Tire (容斥)

题目链接：https://nanti.jisuanke.com/t/A1995
ACM-ICPC 2018 沈阳赛区网络预赛 G.Spare Tire (容斥)
题目大意
根据题目中所给的公式，问在1–n中与m互质的和是多少；

分析题意
通过打表会发现 $a_i$ =(i+1)*i,那么原问题就可以转化成

$\sum_{i=1}^n i(i+1){gcd(i,m)==1}$
但是呢，我们需要知道 $\sum_{i=1}^n i(i+1)$ 的通项公式是什么，通项公式就是：
$\sum_{i=1}^n i(i+1)=\sum_{i=1}^n i^2+i=\dfrac{n*(n+1)*(2*n+1)}{6}+\dfrac{n*(n+1)}{2}$
那么我们可不可以这样去想呢，就是先将1–n的和求出，然后减去与m不互质的，那么剩下的不就是与m互斥的和了吗(✪ω✪)；
但是呢，这里还是有一个问题需要去解决，那就是如何去减去与m不互质的答案呢，其实这里是需要去套一个模板，就是求关于容斥的二进制做法的模板，代码中我也附上了这个板子，有兴趣的可以去模拟一下；

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int MOD=1e9+7;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Abs(x) ((x)>=0?(x):-(x))
ll inv6,tot,m,n,inv2;
vector<ll>fac;
int prime[10010];
bool is_prime[10010];
void getprime(){
    for(int i=2;i<=10000;i++){
        if(!is_prime[i]){
           prime[tot++] =i;
           for(int j=i+i;j<=10000;j+=i)
            is_prime[j]=1;
        }
    }
}
ll qpow(ll base,ll p){
    ll ans=1;
    while(p){
        if(p&1)
         ans=ans*base%MOD;
        p>>=1;
        base=base*base%MOD;
    }
    return ans;
}
void getfac(){
    int cnt=0;//记录多少个素因子
//    cout<<tot<<endl;
    for(int i=0;i<tot&&prime[i]*prime[i]<=m;i++){
        if(m%prime[i]==0){
            fac.push_back(prime[i]);
            while(m%prime[i]==0) m/=prime[i];
        }
        if(m==1) break;
    }
    if(m>1) fac.push_back(m);
}
ll jisuan(ll sum){
        ll k=n/sum;
//		ll p=(1+k)*k%MOD*inv2%MOD*sum%MOD;
//		ll q=k*(k+1)%MOD*(2*k+1)%MOD*inv6%MOD*sum%MOD*sum%MOD;
//    return (p+q)%MOD;
    ll q=k*(k+1)%MOD*(2*k+1)%MOD*inv6%MOD*sum%MOD*sum%MOD+(1+k)*k%MOD*inv2%MOD*sum%MOD;
    return q%MOD;
}
void solve(){
    ll ans=jisuan(1);
    ll s=0;
    for(int i=1;i<(1<<fac.size());i++){
        ll sum=1,cnt=0;
        for(int j=0;j<fac.size();j++){
            if(i&(1<<j)){
                cnt++;
                sum*=fac[j];
            }
        }
        ll p=jisuan(sum);
        if(cnt&1)
            s=(s+p)%MOD;
        else
            s=(s-p+MOD)%MOD;
    }
    printf("%lld\n",(ans-s+MOD)%MOD);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    getprime();
    inv6=qpow(6,MOD-2);
    inv2=qpow(2,MOD-2);
    while(scanf("%lld%lld",&n,&m)!=EOF){
        fac.clear();
        getfac();
        solve();
    }
    return 0;
 }

ACM-ICPC 2018 沈阳赛区网络预赛 G.Spare Tire (容斥)

相关推荐