题目描述
有(n)只青蛙，(m)个围成圆圈的石头。第(i)只青蛙每次只能跳(a_i)个石头，问最后所有青蛙跳过的石头的下标总和是多少？
Input
第一行为(T) 表示数据组数
每一组数据第一行为(n)和(m)
第二行有(n)个整数 表示每只青蛙一步跳的距离
(T<=20,1<=n<=10^4,1<=m<=10^9,1<=a_i<=10^9)
Output
对于每组数据 输出"Case #x: "（不含引号）以及答案
Sample Input
3
2 12
9 10
3 60
22 33 66
9 96
81 40 48 32 64 16 96 42 72
Sample Output
Case #1: 42
Case #2: 1170
Case #3: 1872
很容易就可以想到，每只青蛙可以跳到的石头的编号一定是(gcd(m,a_i))的倍数。
那么问题就变成了，给出(n)个数(B_i)，问小于等于(m)中为(B_i)倍数的数的和为多少。
对于一只青蛙，其能够跳到的石头的编号是一个等差数列。
这个，我们可以利用高斯求和解决，答案就是(((m-1)/B[i]*B[i]*((m-1)/B[i]+1))/2)
然而，我们发现，如果把答案加上所有的青蛙的答案，其中会有很多重复的被算了好几次。
我们需要利用容斥去求解。
我们发现，会造成重复的编号一定是满足两只青蛙具有倍数关系的青蛙，并且由于是(gcd)所以一定是(m)的因子。
所以我们应该从(m)的因子上来考虑。
于是，我们先将(m)的所有因子给求出来。
然后，对于每个青蛙的步长(A_i)并求出(B_i)，枚举(m)的因子，若该因子是青蛙(B_i)的倍数。
则给该因子打一个标记，由于该因子已经被计算过了一次。
所以，其倍数造成的贡献已经被它给计算过了一次，所以要减去他造成的贡献。
但由于，我们无法直接计算一个数多造成的贡献，但可以快速的计算出一个数被因子计算了几次。
既然多算了那么多次，减掉就好了。。。。
于是我们就有了这样的伪算法：
for(i:对于m的因子){
if(该因子已经被计算的次数!=应该被计算的次数){
int temp=该因子已经被计算的次数-应该被计算的次数;
Ans+=temp*贡献。
for(j:对于m的因子)if(j是当前因子i的倍数){
//说明被多计算了。
j已经被计算的次数+=temp;
}
}
}
前面我们已经说过了一个数的贡献，直接计算即可。
代码如下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
#define reg register
#define Raed Read
#define clr(a,b) memset(a,b,sizeof a)
#define Mod(x) (x>=mod)&&(x-=mod)
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)>(b)?(b):(a))
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])
inline int Read(void) {
int res=0,f=1;
char c;
while(c=getchar(),c<48||c>57)if(c=='-')f=0;
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>=48&&c<=57);
return f?res:-res;
}
template<class T>inline bool Min(T &a, T const&b) {
return a>b?a=b,1:0;
}
template<class T>inline bool Max(T &a, T const&b) {
return a<b?a=b,1:0;
}
const int N=1e4+5,M=1e5+5,mod=110119;
bool MOP1;
int A[N],B[N],vis[N],Num[N];
int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
bool MOP2;
inline void _main(void) {
int T=Read(),Case=0;
while(T--) {
int n=Read(),m=Read(),tot=0,Ans=0;
clr(vis,0),clr(Num,0);
for(reg int i=1; i*i<=m; i++)if(!(m%i)) {
B[++tot]=i;
if(i*i!=m)B[++tot]=m/i;
}
sort(B+1,B+tot+1),tot--;
rep(i,1,n) {
A[i]=Read(),A[i]=gcd(A[i],m);
rep(j,1,tot)if(!(B[j]%A[i]))vis[j]=1;
}
rep(i,1,tot) {
if(vis[i]==Num[i])continue;
int Now=(m-1)/B[i],temp=vis[i]-Num[i];
Ans+=(Now*B[i]*(Now+1))*temp/2;
rep(j,1,tot)if(!(B[j]%B[i]))Num[j]+=temp;
}
printf("Case #%lld: %lld
",++Case,Ans);
}
}
signed main() {
_main();
return 0;
}