POJ1006
2691 ワード
伝説の「中国の残りの定理」
質問説明:####
3つの相互質の自然数:a,b,cについて、次の式がすべて成立するように、1つの数xを求める必要があります.
-x%a = m1; -x%b = m2; -x%c = m3;
解法:####
では、
k1 = a * b; k2 = b * c; k3 = a * b; さらにt 1とp 1 t 1=k 1*p 1、t 1%a=0&&t 1%b=0&&t 1%c=1を求める.k 1=a*bのため;したがって、t 1%a=0&&t 1%b=0は明らかに成立する.したがって、t 1%c=1がt 1%c=1になるようにp 1を要求するだけで、t 1%c=1を以下のコードで最後に、x=t 1*m 3+t 2*m 2+t 3*m 1である.x>a*b*cの場合.ではx=x-a*b*c;
証明:####
なぜなら
t1 = k1 * p1, t1 % a = 0 && t1 % b = 0 && t1 % c = 1; t2 = k2 * p2, t2 % a = 0 && t2 % c = 0 && t2 % b = 1; t3 = k3 * p3, t3 % b = 0 && t1 % c = 0 && t3 % a = 1; x = t1 * m3 + t2 * m2 + t3 * m1;
t 1%a=0&&t 1%b=0&&t 1%c=1であるからである.したがって、t 1*m 3%a=0&&t 1*m 3%b=0&&t 1*m 3%c=m 3である.同様に、t 2*m 2%a=0&&t 2*m 2%c=0&&t 2*m 2%b=m 2;t3 * m1 % b = 0 && t3 * m1 % c = 0 && t3 * m1 % a = m1;
したがってx=t 1*m 3+t 2*m 2+t 3*m 1%a:0+0+m 3%b:0+m 2+0%c:m 1+0+0 Over~
実装コード:####
コードは、genParaが生産パラメータ(a,b,c)に使用される
` package poj; import java.util.Scanner; public class Poj1006 { public static void main(String[] args) {//genPara();
}
`
質問説明:####
3つの相互質の自然数:a,b,cについて、次の式がすべて成立するように、1つの数xを求める必要があります.
-x%a = m1; -x%b = m2; -x%c = m3;
解法:####
では、
k1 = a * b; k2 = b * c; k3 = a * b; さらにt 1とp 1 t 1=k 1*p 1、t 1%a=0&&t 1%b=0&&t 1%c=1を求める.k 1=a*bのため;したがって、t 1%a=0&&t 1%b=0は明らかに成立する.したがって、t 1%c=1がt 1%c=1になるようにp 1を要求するだけで、t 1%c=1を以下のコードで
int p1 = 1; for( ; p1 < c ; p1 ++){ t1 = k1 * p1; if(t1 % c == 1) break; } p 1証明:####
なぜなら
t1 = k1 * p1, t1 % a = 0 && t1 % b = 0 && t1 % c = 1; t2 = k2 * p2, t2 % a = 0 && t2 % c = 0 && t2 % b = 1; t3 = k3 * p3, t3 % b = 0 && t1 % c = 0 && t3 % a = 1; x = t1 * m3 + t2 * m2 + t3 * m1;
t 1%a=0&&t 1%b=0&&t 1%c=1であるからである.したがって、t 1*m 3%a=0&&t 1*m 3%b=0&&t 1*m 3%c=m 3である.同様に、t 2*m 2%a=0&&t 2*m 2%c=0&&t 2*m 2%b=m 2;t3 * m1 % b = 0 && t3 * m1 % c = 0 && t3 * m1 % a = m1;
したがってx=t 1*m 3+t 2*m 2+t 3*m 1%a:0+0+m 3%b:0+m 2+0%c:m 1+0+0 Over~
実装コード:####
コードは、genParaが生産パラメータ(a,b,c)に使用される
` package poj; import java.util.Scanner; public class Poj1006 { public static void main(String[] args) {//genPara();
Scanner sc = new Scanner(System.in);
int c = 0;
while (true) {
c++;
int p = sc.nextInt();
int e = sc.nextInt();
int i = sc.nextInt();
int d = sc.nextInt();
if (p == -1 && e== -1 && i == -1 && d == -1)
break;
int ans = (5544 * p + 14421 * e + 1288 * i-d+21252) % 21252;
if(ans==0)
ans=21252;
System.out.println("Case " + c + ": the next triple peak occurs in " + ans + " days.");
}
sc.close();
}
public static void genPara(){
int m1 = 23;
int m2 = 28;
int m3 = 33;
int a = 1;
int b = 1;
int c =1;
int k1 = m2*m3*a;
int k2 = m1*m3*b;
int k3 = m1*m2*c;
for(; a < 23 ; a ++){
k1 = m2*m3*a;
if(k1%m1 == 1)
break;
}
for(; b < 28 ; b ++){
k2 = m1*m3*b;
if(k2%m2 == 1)
break;
}
for(; c < 33 ; c ++){
k3 = m1*m2*c;
if(k3%m3 == 1)
break;
}
System.out.println("k1:"+k1);
System.out.println("k2:"+k2);
System.out.println("k3:"+k3);
}
}
`