YCJSOI3082跑跑步

一道数学题

题目大意:

小胡同学是个爱运动的好孩子。

每天晚上,小胡都会到操场上跑步,学校的操场可以看成一个由 n个格子排成的一个环形,格子按照顺时针顺序从0到n-1标号。

小胡观察到有m个同学在跑步,最开始每个同学都在起点(0号格子),每个同学都有一个步长ai,每跑一步,每个同学都会往顺时针方向前进ai个格子。由于跑道是环形的,如果一个同学站在n-1这个格子上,如果他前进一个格子,他就会来到0。

他们这样在跑道上不知疲倦地跑呀跑呀。小胡同学惊奇地发现,似乎有些格子永远不会被同学跑到,他想知道这些永远不会被任何一个同学的跑到的格子的数目,你能帮帮他吗?(我们假定所有同学都跑到过0号格子)。

题解:

如果一个位置p会被踩到的话,那么需要满足$\exists i$ ,使得$a_i \times x \equiv p (mod \ m)$。

化简一下得到:$a_i \times x - n \times y = p (x,y \in \text{Z} )$。

若要此方程有解,必须满足$gcd(a_i,n)|p$。

令$c_i=gcd(a_i,n),d=gcd(p,n)$。

因为$c_i|p$并且$c_i|n$,因而$c_i$为$n$和$p$的公因子。而$d$为$p$和$n$的最大公因子,则一定$\exists c_i$ ,满足$c_i|d$。

那么对于这道题,思路就变成这样子了:

枚举这个$d$。因为$d$为$n$的因子,因而这里的枚举是$\sqrt n$的。

接下来对于每一个$d$,先判断是否存在一个$c_i$满足条件,若存在,我们计算它对答案的贡献。

对答案的贡献即为求有多少个$p$满足$gcd(p,n)=d$。

化简得$gcd(\frac p d,\frac n d)=1$,也就是求$\varphi(\frac n d ) $。

也就是欧拉公式,我们有$\varphi(i)=i \times (1- \frac 1 {p_1}) \times (1- \frac 1 {p_2}) … $

综上所述,题目即可求解。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
res=0;char c;
while(c=getchar(),c<48);
do res=res*10+(c&15);
while(c=getchar(),c>47);
}
const int N=55;
int n,m,a[N],c[N],ans;
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
vector<int>son;
int phi(int p){
int res=p;
for(int i=0;i<son.size();i++){
if(p%son[i]==0)res=res/son[i]*(son[i]-1);
}
return res;
}
void solve(int d){
bool flag=false;
for(int i=1;i<=m;i++){
if(d%c[i]==0)flag=true;
}
if(!flag)return;
ans+=phi(n/d);
}
const int LIM=50000;
bool is_prime[LIM];
void init(int sum){
memset(is_prime,1,sizeof(is_prime));
is_prime[1]=is_prime[0]=false;
for(int i=2;i<LIM;i++){
if(is_prime[i]){
if(sum%i==0)son.push_back(i),sum/=i;
while(sum%i==0)sum/=i;
for(int j=i+i;j<LIM;j+=i)is_prime[j]=false;
}
}
if(sum!=1)son.push_back(sum);
}
int main(){
Rd(n),Rd(m);
for(int i=1;i<=m;i++){
Rd(a[i]);
c[i]=gcd(a[i],n);
}
init(n);
for(int i=1;1LL*i*i<=n;i++){
if(n%i==0){
solve(i);
if(n/i!=i)solve(n/i);
}
}
printf("%d\n",n-ans);
return 0;
}
分享到 评论