Solution -「HDU 1788」CRT again (mathcal{Description}) (mathcal{Solution})
Link.
解同余方程组：
[xequiv m_i-apmod{m_i}
]
其中 (i=1,2,dots,n)。
(nle10)，(a<m_i<100)，多测（假设常规 CRT 不可过）。
(mathcal{Solution})
显：
[x=operatorname{lcm}(m_1,m_2,cdots,m_n)-a
]
复杂度 (mathcal O(nlogmax{m_i}))（只是优化了常数 www）。
(mathcal{Code})
#include <cstdio>
typedef unsigned long long ULL;
inline ULL gcd ( const ULL a, const ULL b ) { return b ? gcd ( b, a % b ) : a; }
int main () {
int n, a;
while ( ~ scanf ( "%d %d", &n, &a ) && n | a ) {
ULL ans = 1;
for ( int i = 1, m; i <= n; ++ i ) {
scanf ( "%d", &m );
ans *= m / gcd ( ans, m );
}
printf ( "%llu
", ans - a );
}
return 0;
}