題目大意:有n只青蛙，每只青蛙的彈跳能力為ai，他們都從0出發，繞著m個石頭圍成的圈子跳躍，石頭編號為0~m-1，問能被跳到的石頭編號之和

具體思路:首先可以發現彈跳能力為ai的青蛙，可以跳到的石頭編號是gcd(ai, m)的倍數

枚舉m的因子，若某個青蛙可以彈跳的石頭編號中有該因子，那證明編號為這個因子的石頭一定會被跳到

num[i]記錄編號為i的石頭被跳了幾次，如果被跳的次數不等于應跳的次數(不為0或1)，則減去多余的影響

AC代碼

#include<bits/stdc++.h> #define int long long using namespace std; int T,i,j,n,m,vis[100000],num[100000],x,t; int gcd(int a,int b) {if(b==0)return a;else return gcd(b,a%b); } map <int,int> mp; vector <int> d; main() {scanf("%lld",&T);for (int tt=1; tt<=T; tt++){scanf("%lld%lld",&n,&m);int M=(int)sqrt(m);for (i=1; i<=M; i++){if(m%i==0){d.push_back(i);if(m/i!=i)d.push_back(m/i);}}sort(d.begin(),d.end());memset(vis,0,sizeof vis);memset(num,0,sizeof num);for(i = 1; i <= n; ++i){scanf("%lld",&x);t=gcd(x,m);M=d.size();for(j=0; j<M; ++j)if(d[j]%t==0)vis[j]=1;}int ans=0;M=d.size()-1;for(i = 0; i<M; ++i)if(vis[i]!=num[i]){t=(m-1)/d[i];ans+=t*(t+1)/2*d[i]*(vis[i]-num[i]);t=vis[i]-num[i];for(j = i; j <M; ++j)if(d[j]%d[i]==0)num[j]+=t;}printf("Case #%lld: %lld\n",tt,ans);}return 0; }

?

轉載于:https://www.cnblogs.com/Orange-User/p/7767020.html

總結

以上是生活随笔為你收集整理的HDU - 5514 Frogs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。