hdoj 1573 X 문제 [CRT] [방정식 풀이 팀 이 N 내 정수 에서 풀 수 있 는 개수]

X 문제 시간 제한: 1000 / 1000 MS (Java / 기타)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4405    Accepted Submission(s): 1420
Problem Description
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).
 
Input
데 이 터 를 입력 하 는 첫 번 째 행 위 는 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 입 니 다.각 조 테스트 데이터 의 첫 번 째 행 위 는 두 개의 정수 N, M (0 < N < = 1000, 000, 000, 0 < M < = 10) 으로 X 가 N 보다 작 음 을 나타 내 고 배열 a 와 b 에는 각각 M 개의 요소 가 있다.다음 두 줄 은 각 줄 에 각각 M 개의 정수 가 있 는데 각각 a 와 b 중의 요소 이다.
 
Output
각 그룹의 입력 에 대응 하여 독립 된 줄 에 하나의 정 수 를 출력 하여 조건 을 만족 시 키 는 X 의 개 수 를 표시 합 니 다.
 
Sample Input

       
       
       
       

        
        
        
        3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9
       
       
       
       

 
Sample Output

       
       
       
       

        
        
        
        1
0
3
       
       
       
       

 
CRT 가 방정식 그룹 을 합병 할 때 계수 의 변 화 를 파악 하면 KO 라 는 문 제 를 풀 수 있다.
n - 1 회 합병 한 후에 우 리 는 이러한 방정식 그룹 a * x = c (mod lcm) 중 lcm = (m [0], m [1], m [2]... m [n - 1] 을 얻 었 다.
내 코드 가 CRT 에서 되 돌아 온 것 은 - 1 또는 가장 작은 정수 분해 temp 이다.
그러면 우리 가 분류 하여 토론 해 야 할 상황:
1, 반환 - 1, 무 해 출력 0;
2, temp > N, 무 해 출력 0;여기 N 은 문제 의 크기 제한 입 니 다.
3, temp < N, 출력 (N - temp) / lcm + 1.
   (1) 최소 비 마이너스 0, 이때 temp = lcm, 마지막 답 N / lcm = (N - lcm) / lcm + 1 = (N - temp) / lcm + 1.
   (2) 최소 비 마이너스 비 0, 이때 temp + k * lcm < = N, 마지막 답 (N - temp) / lcm + 1.
AC 코드:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 20
#define LL long long
using namespace std;
LL gcd(LL a, LL b){
    return b == 0 ? a : gcd(b, a%b);
}
void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(b == 0) {d = a, x = 1, y = 0;}
    else
    {
        exgcd(b, a%b, d, y, x);
        y -= x * (a / b);
    }
}
LL lcm;//      m   LCM
LL CRT(LL l, LL r, LL *m, LL *a)
{
    lcm = 1;
    for(LL i = l; i <= r; i++)
        lcm = lcm / gcd(lcm, m[i]) * m[i];
    for(LL i = l+1; i <= r; i++)
    {
        LL A = m[l], B = m[i], d, x, y, c = a[i] - a[l];
        exgcd(A, B, d, x, y);
        if(c % d)
            return -1;
        LL mod = m[i] / d;
        LL k = ((x * c / d) % mod + mod) % mod;
        a[l] = m[l] * k + a[l];
        m[l] = m[i] / d * m[l];
    }
    if(a[l] == 0)
        return lcm;
    return a[l];
}
LL m[MAXN], a[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        LL n, N;
        scanf("%lld%lld", &N, &n);
        for(LL i = 0; i < n; i++)
            scanf("%lld", &m[i]);
        for(LL i = 0; i < n; i++)
            scanf("%lld", &a[i]);
        LL temp = CRT(0, n-1, m, a);
        if(temp == -1 || temp > N)//  
            printf("0
");
        else
        {
            LL ans = (N - temp) / lcm + 1;
            printf("%lld
", ans);
        }
    }
    return 0;
}