YCJSOI3082跑跑步

YCJSOI
数论

一道数学题

题目大意：

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

每天晚上，小胡都会到操场上跑步，学校的操场可以看成一个由 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;
}
分享到 评论