ACM-ICPC 2017 Asia Urumqi Sum of the Line(容斥原理)

题目链接：https://nanti.jisuanke.com/t/28970

题目大意：1~k中与k不互质的数字取0，求这个序列的后缀和，然后对后缀和加和求结果

题目思路：很明显最后一个数字会被k个数字都当作后缀和的加数，倒数第二个会被k-1个，所以如果单单是1~k的后缀和，应该是 $\sum_{i=1}^k i^2$ ,易知该和等于 $\frac{n*(n+1)*(2*n+1)}{6}$ ,所以我们现在需要去掉与k不互质的数字造成的影响。用刚才那个理论很容易得出，去掉一个数字对该和的影响只需减去该数字的平方。所以我们只需要获得k的质因数，他的质因数的倍数都是要被去掉的。但是这里还有一个需要注意的地方，那就是可能会减重了，比如6既是2的倍数又是3的倍数，所以这里我们需要用到容斥，如果一共有num个数字，那么就是一共有 $2^{num}$ -1种情况(不能一个都不要，所以0需要被排除)，只需要用1~ $2^{num}$ 的十进制所对应的二进制就能表示所有情况，奇加偶减。 $\sum_{i=1}^{i*p<=k} (i*p)^2$ 由这个公式发现，将 $p^2$ 提取出来以后，就变成了 $\sum_{i=1}^{k/p} i^2$ 然后减掉这些就行了。

以下是代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 100005
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define MOD 998244353
int factor[15],num;
ll quickpow(ll x,ll y){if(!y)return 1;ll temp=quickpow(x,y/2);temp*=temp;temp%=MOD;if(y&1){temp*=x;temp%=MOD;}return temp;
}
ll six=quickpow(6,MOD-2);
void solve(int n){rep(i,2,sqrt(n)){if(n%i==0){factor[num++]=i;while(n%i==0)n/=i;}}if(n>1)factor[num++]=n;
}
ll sum(ll n){ll ans=(((((n*(n+1))%MOD)*(2*n+1))%MOD)*six)%MOD;return ans;
}
int main(){int t,k;scanf("%d",&t);while(t--){num=0;scanf("%d",&k);solve(k);ll ans=sum(k),temp=0;rep(i,1,(1<<num)-1){int cnt=0,t=1;ll anss=1;rep(j,0,num-1){if(i&t){anss=(factor[j]*anss)%MOD;cnt++;}t<<=1;}if(cnt&1){temp=(temp+(((anss*anss)%MOD)*sum(k/anss)))%MOD;}else{temp=(temp-(((anss*anss)%MOD)*sum(k/anss)))%MOD;}}ans=(ans-temp+MOD)%MOD;printf("%lld\n",ans);}return 0;
}