hdu 1573 X问题 (exgcd求解一般线性同余方程组解的个数)

题目链接

题意:求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

思路:先用扩展欧几里得算法(excrt)解一般同余方程求出一个特解R,然后通解R’ = R + k * LCM(a1..am)

注意一些特殊情况,如果无解输出0,如果n小于最小的正整数的R也输出0,

否则答案为(n-R)/M + 1

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz