HDU 5514

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：给你 N 个数和一个 M；

对于每一个 Ni ，乘以 K 取摸 M 都有一个集合，把所有集合合并，求和

Σ ai ( ai → K * Ni % M )

思路：最开始直接求一边gcd ，然后容斥。。。。结果状态有 2 ^ （1e4）....

反着求 M 的约数，然后记录要用到的约数，对于这些进行容斥就好了（不能状压）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 131;
LL gcd(LL a, LL b){
return b == 0 ? a : gcd(b, a % b);
}LL P[maxn], cnt;
void GetP(LL m){
cnt = 0;
for(LL i = 1; i <= sqrt(m); ++i)
{
if(m % i == 0)
{
P[cnt++] = i;
if(i * i != m) P[cnt++] = m / i;
}
}
sort(P,P+cnt);
}LL Vis[maxn], Num[maxn];int main()
{
int T;
scanf("%d", &T);
for(int kase = 1; kase <= T; ++kase)
{
LL n, m;
scanf("%lld %lld", &n, &m);
GetP(m);
LL u;
memset(Vis,0, sizeof(Vis));
memset(Num,0, sizeof(Num));
for(int i = 0; i < n; ++i)
{
scanf("%lld", &u);
LL tmp = gcd(u, m);
for(LL j = 0; j < cnt; ++j)
{
if(P[j] % tmp == 0)
Vis[j] = 1;
}
}
//cout << P[cnt - 1 ] << endl;
Vis[cnt -1] = 0;
LL Ans = 0;
for(LL i = 0; i < cnt; ++i) // 容斥
{
if(Vis[i] != Num[i])
{
LL tmp = m / P[i], D = Vis[i] - Num[i];
Ans += (tmp + 1) * tmp / 2 * P[i] * D;
for(LL j = i; j < cnt; ++j)
{
if(P[j] % P[i] == 0)
Num[j] += D;
}
}
}printf("Case #%d: %lld\n", kase, Ans);
}
}