wordpress资讯网站模板,wordpress根目录,中卫网架配件多少钱,南山网站建设找哪家公司好正题
题目链接:https://www.luogu.com.cn/problem/P5887?contestId24709 题目大意 nnn个洞围成一个环#xff0c;兔子每次会往前跳kkk个洞#xff0c;mmm只兔子给出其实位置#xff0c;求有多少个洞不会被经过。 解题思路
我们可以发现kxnyckxnyckxnyc#xff0c;有c∣g…正题
题目链接:https://www.luogu.com.cn/problem/P5887?contestId24709 题目大意
nnn个洞围成一个环兔子每次会往前跳kkk个洞mmm只兔子给出其实位置求有多少个洞不会被经过。 解题思路
我们可以发现kxnyckxnyckxnyc有c∣gcd(k,n)c|gcd(k,n)c∣gcd(k,n)。
那么对于每个兔子的起点ppp可以覆盖任何z∗gcd(k,n)p‘在这里插入代码片‘(z∈N)z*gcd(k,n)p在这里插入代码片(z\in N)z∗gcd(k,n)p‘在这里插入代码片‘(z∈N)所以我们开一个大小为gcd(k,n)gcd(k,n)gcd(k,n)的桶就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,m,k,z,p,ans;
bool v[1100000];
int main()
{scanf(%d%d%d,n,m,k);z__gcd(n,k);for(int i1;im;i){scanf(%d,p);v[p%z]1;}for(int i0;iz;i)if(!v[i]) ansn/z;printf(%d,ans);
}
