HDU 1576：A/B
1922 단어 HDU
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2811 Accepted Submission(s): 2079
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
쇠뿔 도 단 김 에 빼 고 유클리드 를 확장 하 는 문제 도 간단 하 다.
(n=A%9973)번역 하면 A=9973*X+n (1)
구 하 는 y=(A/B)%9973 번역 하면 A/B=9973*Z+y (2)여기 주의 하 세 요.우리 가 요구 하 는 것 은 y 입 니 다.
(1)(2)식 을 통 해 A 는 모 르 기 때문에 A 를 없 애 야 한다.(정말 고등학교 문 제 를 푸 는 느낌 이 든다...)얻 은 방정식 정 리 는 바로...
9973*(Z*B-X) +B*y = n
gcd(9973,B)=1 이 라 고 알려 져 있 습 니 다.다행 입 니 다.이 조건.우 리 는(Z*B-X)부분 에 관심 이 없 기 때문에 Y 만 을 바 랍 니 다.그래서(Z*B-X)를 미지수 로 생각하면 되 고,확장 유클리드 는 A 로 떨어진다.
코드:
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int xx,yy,yue;
int a,b,d;
void ex_gcd(int a,int b, int &xx,int &yy)
{
if(b==0)
{
xx=1;
yy=0;
yue=a;
}
else
{
ex_gcd(b,a%b,xx,yy);
int t=xx;
xx=yy;
yy=t-(a/b)*yy;
}
}
int main()
{
int test;
cin>>test;
while(test--)
{
long long n,B;
cin>>n>>B;
ex_gcd(9973,B,xx,yy);
yy=yy*n;
yy=(yy%9973+9973)%9973;
cout<<yy<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
