題目

小胡同學是個熱愛運動的好孩子。
每天晚上，小胡都會去操場上跑步，學校的操場可以看成一個由n個格子排成的一個環形，格子按照順時針順序從0 到n- 1 標號。
小胡觀察到有m 個同學在跑步，最開始每個同學都在起點（即0 號格子），每個同學都有個步長ai，每跑一步，每個同學都會往順時針方向前進ai 個格子。由于跑道是環形的，如果一個同學站在n-1 這個格子上，如果他前進一個格子，他就會來到0。
他們就這樣在跑道上上不知疲倦地跑呀跑呀。小胡同學驚奇地發現，似乎有些格子永遠不會被同學跑到，他想知道這些永遠不會被任何一個同學跑到的格子的數目，你能幫幫他
嗎？（我們假定所有同學都跑到過0 號格子）。

分析

首先對于一個人 i, 顯然，那么它所能到達的格子一定是$gcd(ai,n) \(的倍數。 所以我們枚舉n的約數d，如果有一個i，\)gcd(a_i,n)|d\(,說明所有\)gcd(j,n) = d$ 的格子都能被到達，答案加上 \(φ(\dfrac{n}ze8trgl8bvbq)\) 即可。

#include <cmath> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> const int maxlongint=2147483647; const int mo=1000000007; const int N=55; using namespace std; int a[N],n,m,ans; int gcd(int x,int y) {if(y==0) return x; if(x<y) return gcd(y,x); else return gcd(y, x%y); } int phi(int x) {int sum=x,e=x;for(int i=2;i<=int(sqrt(e));i++){if(x%i==0){sum=sum/i*(i-1);while(x%i==0) x/=i;}}if(x>1){sum=sum/x*(x-1);}return sum; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d",&a[i]);for(int i=1;i<=int(sqrt(n));i++){if(n%i==0){for(int j=1;j<=m;j++)if(i%gcd(a[j],n)==0){ans+=phi(n/i);break;}for(int j=1;j<=m;j++)if((n/i)%gcd(a[j],n)==0){ans+=phi(i);break;}}}cout<<n-ans<<endl; }

轉載于:https://www.cnblogs.com/chen1352/p/9065037.html

總結

以上是生活随笔為你收集整理的【NOIP2016提高A组五校联考2】running的全部內容，希望文章能夠幫你解決所遇到的問題。

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