https://www.nowcoder.com/acm/contest/160/A
题目描述
有一个计数器，计数器的初始值为0，每次操作你可以把计数器的值加上a1,a2,...,an中的任意一个整数，操作次数不限（可以为0次），问计数器的值对m取模后有几种可能。
输入描述:
第一行两个整数n,m接下来一行n个整数表示a1,a2...an
1≤n≤1001≤m,a1,a2,...,an≤1000000000
输出描述:
输出一个整数表示答案
示例1
输入
复制
3 6
6 4 8
输出
复制
3题解：由题意可得：是求(a1*k1+a2*k2+...an*kn)%m的可能值的个数。 首先看(a1*k1+a2*k2+...an*kn)，假设值等于 p，即(a1*k1+a2*k2+...an*kn)=p,设gcd(a1,a2,...an)=d,根据裴蜀定理，p会是gcd(a1,a2,...an)的所有倍数值（也就是p=d*x），
然后再看d*x%m，设d*x%m=t,也就是dx-m*y=t,这个t的可能值的个数也就是答案，而再次根据裴蜀定理，t是gcd(d,m)的倍数值，所以t的最终个数==m/gcd(m,d)=m/gcd(a1,a2,..an,m)
1 #include<bits/stdc++.h>
2 using namespace std;
3 int m;
4 int gcd(
int a,
int b)
5 {
6 return a % b ==
0 ? b : gcd(b , a %
b);
7 }
8 int main()
9 {
10 int n;scanf(
"%d%d",&n,&
m);
11 int g =
m;
12 for(
int i =
1;i <= n;i++
){
13 int q;scanf(
"%d",&
q);
14 g =
gcd(g , q);
15 }
16 printf(
"%d\n",m/
g);
17 return 0;
18 }
View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/9683399.html
