[POJ 2891] Strange Way to Express Integers(중국 잉여정리 확장)
Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?
Solution
중국의 잉여정리를 확장하는 판자문제
증명하면 지프2000 블로그를 볼 수 있어요. 개인적인 느낌으로는 좀 더 분명하게 말한 것 같아요.
데이터를 한 번에 입력하는 것이 좋습니다. 이 문제의 RE는 Break을 풀지 않은 후에 남은 데이터를 읽지 못했기 때문일 수 있습니다.
#include
#include
#include
#include
#define MAXN 50005
using namespace std;
typedef long long LL;
LL k,c[MAXN],m[MAXN];
LL read()
{
LL x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
void exgcd(LL a,LL b,LL &d,LL &x,LL& y)
{
if(!b)d=a,x=1,y=0;
else exgcd(b,a%b,d,y,x),y-=x*(a/b);
}
LL inv(LL a,LL p)
{
LL d,x,y;exgcd(a,p,d,x,y);
return (x+p)%p==0?p:(x+p)%p;
}
int main()
{
LL m1,m2,c1,c2;
while(~scanf("%lld",&k))
{
for(int i=1;i<=k;i++)
m[i]=read(),c[i]=read();
for(int i=2;i<=k;i++)
{
m1=m[i-1],m2=m[i],c1=c[i-1],c2=c[i];
LL t=gcd(m1,m2);
if((c2-c1)%t!=0){c[k]=-1;break;}
m[i]=m1*m2/t;
c[i]=inv(m1/t,m2/t)*((c2-c1)/t)%(m2/t)*m1+c1;
c[i]=(c[i]%m[i]+m[i])%m[i];
}
printf("%lld
",c[k]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.