题意：有n只青蛙，m个石头(围成圆圈)。第i只青蛙每次只能条ai个石头，问最后所有青蛙跳过的石头的下标总和是多少？
题解：暴力肯定会超时，首先分解出m的因子，自己本身不用分，因为石头编号是0到m-1，第i只青蛙只能走到gcd(ai, m)的位置，我们就可以把m的因子提取出来，然后对青蛙能走到的因子位置打标记。两个数组，第一个数组a代表是否能走到该因子，第二个数组b表示是否已经加过了，加过了几次，遍历到那个因子的时候要加上(a[i]-b[i])倍的数，这个数很可能是负数。至于公式利用等差数列前n项和可以得出。
注意这道题是因子分解而不是素因子分解，因为对于12来说2和4是不一样的。
注意这道题不是对数进行操作而是对因子进行操作。
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } const int maxn=1e5+5; ll cnt=0,prime[maxn]; void solve(ll m) { cnt=0;//注意初始化 prime[cnt++]=1; for(int i=2; i<sqrt(m); i++) { if(m%i==0) { prime[cnt++]=i; prime[cnt++]=m/i; } } ll tmp=sqrt(m); if(tmp*tmp==m) prime[cnt++]=tmp; sort(prime,prime+cnt); } int main() { int t,cas=1; scanf("%d",&t); while(t--) { ll n,m,data,tmp; scanf("%lld%lld",&n,&m); memset(prime,0,sizeof(prime)); solve(m); ll a[maxn],b[maxn]; memset(a,0,sizeof(a));//标记 memset(b,0,sizeof(b));//算过了几次 for(int i=0; i<n; i++) { scanf("%lld",&data); tmp=gcd(data,m); for(int j=0; j<cnt; j++) { if(prime[j]%tmp==0) a[j]=1; } } ll ans=0; for(int i=0; i<cnt; i++) { ll num=a[i]-b[i]; if(num!=0) { ll tmp=(m-1)/prime[i]; ans=ans+tmp*(tmp+1)/2*prime[i]*num; for(int j=i; j<cnt; j++) { if(prime[j]%prime[i]==0) b[j]=b[j]+num; //注意是b表示数目 } } } printf("Case #%d: %lld ",cas++,ans); } return 0; }
更新版：
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } const int maxn=1e5+5; ll prime[maxn],a[maxn]; int cnt=0; void solve(ll m) { memset(a,0,sizeof(a)); memset(prime,0,sizeof(prime)); cnt=0; prime[cnt++]=1; for(int i=2;i<sqrt(m);i++) { if(m%i==0) { prime[cnt++]=i; prime[cnt++]=m/i; } } if(ll(sqrt(m))*ll(sqrt(m))==m) prime[cnt++]=ll(sqrt(m)); sort(prime,prime+cnt); } int main() { int t,cas=1; scanf("%d",&t); while(t--) { ll n,m,data; scanf("%lld%lld",&n,&m); solve(m); for(int i=0;i<n;i++) { scanf("%lld",&data); data=gcd(data,m); for(int j=0;j<cnt;j++) if(prime[j]%data==0) a[j]=1; } ll ans=0; for(int i=0;i<cnt;i++) { ll num=a[i]; if(num!=0) { ll tmp=(m-1)/prime[i]; ans+=tmp*(tmp+1)/2*prime[i]*num; for(int j=i+1;j<cnt;j++) if(prime[j]%prime[i]==0) a[j]-=num; } } printf("Case #%d: %lld ",cas++,ans); } return 0; }