ACM-ICPC 2018 沈阳赛区网络预赛 G. Spare Tire
这题很好啊，好在我没做出来。。。大概分析了一下，题目大概意思就是求
问所有满足1<=i<=n且i与m互素的ai之和
最开始我们队的做法是类似线性筛的方法去筛所有数，把数筛出来后剩下数即可，但是这样的是时间复杂度十分大，我们需要遍历每个质因
的倍数，这样最坏的复杂度是很大的1e8，因为我们需要把i的倍数筛到1e8，这样肯定不行，那么想想其他办法
我们想到了容斥-----（赛后想到的）
我们可以推处一个公式ai=i*i+i;
那么ai的前n项和Tn=n*(n+1)*(2*n+1)/6+n*(n+1)/2;
我们知道了前N项和，再减去和M不互质的数的贡献即可，那么怎么利用上面式子算贡献呢？？？
根据算数基本定理将m分解，与m不互素的就是至少有其中一个因子，算所有的所以要容斥
对于每个因子积sum，会形成sum,2*sum,3*sum...[n/sum]*sum这些不互素的数，
设k=[n/sum],我们把这些数提出一个sum
那么这些数变成了sum*(1+2+3+....+k)那么在这个sum下，这个贡献T=k*(k+1)*(2*k+1)/6*i*i+k*(k+1)/2*i;
有人回想为什么？？需要乘以i*i和i呢？？我们可以看一下原来的an=i*i+i；那么前an=(k*i)*(k*i)+k*i=i*i*k*k+k*i;
如果没看懂，可以看看这个
https://blog.csdn.net/lngxling/article/details/82530798
我的代码
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #define ll long long using namespace std; const ll mod = 1e9+7; ll inv6=166666668; ll inv2=500000004; ll a[10005]; ll sum(ll n,ll i){ n=n/i; ll ans=((n%mod)*(n+1)%mod*(2*n+1)%mod*inv6%mod*i%mod*i%mod+n%mod*(n+1)%mod*inv2%mod*i%mod)%mod; return ans; }; int main(){ long long n,m; int cnt; int num[20]; while(~scanf("%lld%lld",&n,&m)){ int tmp=m; cnt=0; while(tmp!=1){ int flag=0; for (int i=2;i<=sqrt(m);i++){ if (tmp%i==0){ num[cnt]=i; cnt++; flag=1; } while(tmp%i==0){ tmp/=i; } //cout<<"--"<<endl; } if(flag==0 && tmp!=1){ num[cnt]=tmp; cnt++; break; } } ll ans=sum(n,1); ll ans2=0; //cout<<"--"<<endl; for (int i=1;i<(1<<cnt);i++){ int flag=0; ll temp=1; for (int j=0;j<cnt;j++) if (i&(1<<j)) { // cout<<"--"<<endl; flag++; temp=temp*num[j]%mod; } // cout<<"---"<<endl; temp=sum(n,temp); //cout<<"---"<<endl; if (flag%2==1) { ans2=(ans2%mod+temp%mod)%mod; }else { ans2=(ans2%mod-temp%mod+mod)%mod; } } printf("%lld\n",(ans%mod-ans2%mod+mod)%mod); } return 0; }
投递虾皮信息等公司10个岗位 >
Momenta公司福利 296人发布