[수론]HDU 1576

A/B
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4659 Accepted Submission(s): 3627
Problem 설명 요구(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)가 있다.출력 은 각 그룹의 데이터 출력(A/B)%9973 에 대응 합 니 다.
Sample Input 2 1000 53 87 123456789
Sample Output 7922 6060
좋아,나 는 이것 이 간단 한 역 원 을 구 하 는 문제 라 는 것 을 인정한다.
ab=a∗x  mod m
다른 방식 으로 말하자면
a∗b−1=a∗x  mod m
b∗x=1  mod m
이것 이 바로 유클리드 를 확장 하 는 것 이 아니 냐!!
b∗x+m∗y=1  mod m
유클리드 확장 에 대해 서 는 참고 하 시기 바 랍 니 다.
다음은 코드:

#include
#include
#include
#include
#include
using namespace std;

#define MAXN
#define MAXM
#define MOD 9973
#define INF 0x3f3f3f3f
typedef long long int LL;

LL A,B;

LL exgcd(LL a,LL b,LL &x,LL&y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }

    LL rn=exgcd(b,a%b,x,y);
    LL t=x;
    x=y;
    y=t-(a/b)*y;
    return rn;
}

LL getny(LL a,LL mod)
{
    LL x,y;
    exgcd(a,mod,x,y);

    x=x%MOD;
    if(x<0)x+=mod;

    return x;
}

int main()
{
    int Case;
    scanf("%d",&Case);

    while(Case--)
    {
        scanf("%I64d%I64d",&A,&B);
        printf("%I64d
",((A*getny(B,MOD)%MOD)%MOD));
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU 5608] function

Problem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaut...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[수론]HDU 1576

좋은 웹페이지 즐겨찾기