HDU 1576 A/B [유클리드 알고리즘 확장 + 탐색 법]

A/B
 
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6867    Accepted Submission(s): 5457
 
 
Problem Description
요구 (A/B)% 9973, 그러나 A 가 매우 크기 때문에 우 리 는 n (n = A% 9973) 만 제시 합 니 다. (우리 가 정 한 A 는 반드시 B 에 의 해 제 거 될 수 있 고 gcd (B, 9973) = 1).
 
 
Input
데이터 의 첫 줄 은 T 로 T 조 데이터 가 있 음 을 나타 낸다.각 그룹의 데 이 터 는 두 개의 수 n (0 < = n < 9973) 과 B (1 < = B < = 10 ^ 9) 가 있다.
 
 
Output
각 그룹의 데이터 출력 (A/B)% 9973 에 대응 합 니 다.
 
 
Sample Input

2 1000 53 87 123456789
 
 
Sample Output

7922 6060
 
 
Author
xhd
 
 
Source
HDU 2007-1 Programming Contest
 
 
 
 
질문 링크: HDU 1576 A/B
문제 약술: 윗글 참조.
문제 분석:
이 문 제 는 두 가지 해법 이 있 는데, 하 나 는 유클리드 알고리즘 을 확장 하 는 것 이 고, 다른 하 나 는 탐색 법 을 사용 하 는 것 이다.뒤의 방법 이 더 빠 른 것 같다.
 
해법 1: 정수 가 정 해 지지 않 은 방정식 으로 해결 할 수 있 습 니 다. 즉, 확장 유클리드 알고리즘 을 사용 할 수 있 습 니 다.
제목 에 따라 입력 한 n = A% 9973 (A 입력 없 음), A% B = 0 (A 는 반드시 B 에 의 해 정 제 될 수 있 음), B 와 9973 호신 (GCD (B, 9973) = 1).
문제 풀이 과정 은 먼저 방정식 을 만 든 후에 야 프로그램 을 작성 할 수 있다.
x = (A/B)% 9973 (x 는 최종 적 으로 계산 하고 자 하 는 값) 을 설정 하면 9973 k + x = A/B (k 는 정수), A = 9973 Bk + xB 를 얻는다.
n = A% 9973 과 A = 9973 Bk + xB 이기 때문에 xB% 9973 = n, xB = n + 9973 y 를 얻 었 습 니 다.
그러므로 (x/n) B + (- y/n) 9973 = 1 = GCD (B, 9973), 이 방정식 은 풀이 가 있다.
x 와 y 를 요구 하고 먼저 X = x/n 과 Y = - y/n, 즉 방정식 BX + 9973 Y = 1 을 구한다.
마지막 으로 x = X * n.
주의해 야 할 것 은 구 한 x 가 마이너스 일 수 있 으 므 로 조정 이 필요 하 다 는 것 이다.
하지만 이 계산 방법 은 시간 이 좀 걸 리 는 것 같 습 니 다.
 
해법 2: 탐색 법
제목 에 따라 입력 한 n = A% 9973 (A 입력 없 음), A% B = 0 (A 는 반드시 B 에 의 해 정 제 될 수 있 음), B 와 9973 호신 (GCD (B, 9973) = 1).
문제 풀이 과정 은 먼저 방정식 을 만 든 후에 야 프로그램 을 작성 할 수 있다.
x = (A/B)% 9973 (x 는 최종 적 으로 계산 하고 자 하 는 값 으로 0 < = x < = 9972) 을 만족 시 키 면 9973 k + x = A/B (k 는 정수), A = 9973 Bk + xB 를 얻는다.
n = A% 9973 과 A = 9973 Bk + xB 이기 때문에 xB% 9973 = n, xB = n + 9973 y 를 얻 었 고 xB - n = 9973 y 도 얻 었 다.
그러므로: (xB - n)% 9973 = 0
상식 에 대해 서 는 탐색 법 만 사용 하면 x 를 구 할 수 있다.이렇게 해서 프로그램의 운행 속도 가 상당히 빠르다.
아이디어 가 필요 한 것 은 변수 유형 이 롱 일 때 AC 가 없고 롱 롱 으로 바 뀌 면 AC 가 되 는 것 이 이상 하 다 는 것 이다.평가 시스템 이 사용 하 는 컴 파일 버 전의 log 형식 이 64 비트 가 아니 어서 그런 것 일 수도 있 습 니 다.유클리드 알고리즘 을 확장 하여 이 문 제 를 푸 는 방법 은 시간 적 으로 비교적 느리다.탐색 법도 때때로 고 효율 적 이다.
 
 
 
 
 
프로그램 설명: (약).
 
AC 의 C 언어 프로그램 은 다음 과 같 습 니 다 (해법 2).
 

#include   
  
int main(void)  
{  
    int t, i, j;  
    long long n, b, a=9973;  
  
    scanf("%d", &t);  
    for(i=0; i

　
 
 
 
AC 의 C 언어 프로그램 은 다음 과 같 습 니 다 (해법 1).
 

#include 

//              
long exgcd(long a, long b, long *x, long *y)
{
    long x0=1, y0=0, x1=0, y1=1;
    long r, q;
    *x=0;
    *y=1;

    r = a % b;
    q = (a - r) / b;
    while(r)
    {
        *x = x0 - q * x1;
        *y = y0 - q * y1;
        x0 = x1;
        y0 = y1;
        x1 = *x;
        y1 = *y;

        a = b;
        b = r;
        r = a % b;
        q = (a - r) / b;
    }
    return b;
}

int main(void)
{
    int t, i;
    long n, b, a=9973, x, y;

    scanf("%d", &t);
    for(i=0; i