有一个计数器,计数器的初始值为0,每次操作你可以把计数器的值加上a1,a2,...,an中的任意一个整数,操作次数不限(可以为0次),问计数器的值对m取模后有几种可能。
输入描述:
第一行两个整数n,m
接下来一行n个整数表示a1,a2,...,an1≤n≤1001≤m,a1,a2,...,an≤1000000000
输出描述:
输出一个整数表示答案
示例1
输入
3 66 4 8
输出
3
思路:
在数论中,裴蜀定理是一个关于(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何a、b和它们的最大公约数d,关于未知数x和y的线性(称为裴蜀):
ax + by = m
有解m是d的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解x、y都称为裴蜀数,可用求得。
例如,12和42的最大是6,则方程12x + 42y = 6有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。
特别来说, ax + by = 1 有解整数a和b互素。
裴蜀也可以用来给定义:d其实就是最小的可以写成ax + by形式的正整数。这个定义的本质是中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。
对任意两个a、b设d是它们的。那么关于x和y的线性丢番图方程(称为裴蜀等式):
ax + by = m
有整数解(x,y)m是d的倍数。裴蜀等式有解时必然有无穷多个解。
以上定理可推广到n个,n≥2
如1st IMO 1959第1题:证明对任意自然数n,(21n+4)/(14n+3)为分数。证明:很容易看出3(14n+3)-2(21n+4)=1,由裴蜀定理,21n+4与14n+3,故(21n+4)/(14n+3)为既约分数。
另如:5x+4y+3z可表示全部.因为3,4,5互质,所以5x+4y+3z可以等于1,则必定可以等于其他任意整数。
代码如下:
#include#include #include using namespace std;int gcd(int a,int b){ if(b == 0) return a; return gcd(b,a%b);}int main(){ int n,m,x; cin >> n >> m; int count = m; for(int i = 0;i < n;i ++) { cin >> x; count = gcd(x,count); } cout << m / count ; return 0;}