很簡單的一道題目,但是引出了很多知識點。
這是一道中國剩余問題,先貼一下1006的代碼。
#include "stdio.h"
#define MAX 21252
int main()
{
?
? ? int p , e , i , d , n = 1 , days = 0;
?
? ? while(1)
? ? {
? ? ? ? scanf("%d %d %d %d",&p,&e,&i,&d);
?
? ? ? ? if( p == -1 && e == -1 && i == -1 && d == -1)
? ? ? ? ? ? break;
?
? ? ? ? days = (/*28*33*gcd1(28*33,23)*/5544 * p + /*23*33*gcd1(23*33,28)*/14421 * e + /*23*28*gcd1(23*28,33)*/1288 * i + MAX - d)% MAX ;
?
? ? ? ? if(days == 0)
? ? ? ? ? ? days = MAX ;
?
? ? ? ? printf("Case %d: the next triple peak occurs in %d days.\n",n,days);
?
? ? ? ? n++;
?
? ? }
? ? return 1;
}
?
?
乘法逆元的求解方式
?
Extended Euclid (d,f) //算法求d關于模f的乘法逆元d-1 ,即 d* d-1 mod f = 1
1 。(X1,X2,X3) := (1,0,f); (Y1,Y2,Y3) := (0,1,d)
2。 if (Y3=0) then return d-1 = null //無逆元
3。 if (Y3=1) then return d-1 = Y2 //Y2為逆元
4。 Q := X3 div Y3 //整除
5。 (T1,T2,T3) := (X1 - Q*Y1,X2 - Q*Y2,X3 - Q*Y3)
6 。(X1,X2,X3) := (Y1,Y2,Y3)
7。 (Y1,Y2,Y3) := (T1,T2,T3)
8。 goto 2
code:
#include "stdio.h"
?
long gcd1(long a, long p) ? ?//求a關于p的逆元,歐幾里德算法
{
? ? long c , d = a;
? ? long q0 = 0 , q1 = 1 , q2;
? ? do{
? ? ? ? c = a%p;
? ? ? ? if(c)
? ? ? ? q2 = -1*a/p*q1+q0;
? ? ? ? q0 = q1;
? ? ? ? q1 = q2;
? ? ? ? a = p;
? ? ? ? p = c;
? ? ? ? }while(c);
? ? ? ? return q2>0?q2:q2+d;
}
?
int main()
{
? ? long a,b,i;
? ? while(1)
? ? {
? ? ? ? scanf("%d%d", &a, &b);
? ? ? ? if (a==0 && b==0)
? ? ? ? ? ? break;
? ? ? ? printf("%d\n",gcd1(b,a));
? ? }
}
?
窮舉的方式求逆元:
code:
#include "stdio.h"
?
?
long int gcd( long int a , long int p );
?
?
?
?
int main() ? ? ? ?//求a關于p的逆元,a關于p的逆元在(1,p-1)之中 ? 所以用窮舉的方法來求解
{
? ? long int interver;
? ? interver = gcd( 35 , 3 );
?
? ? printf("%ld",interver);
?
? ? return 1 ;
}
?
?
long int gcd( long int a , long int p )
{
?
? ? long int interver = 0 , j;
?
? ? for( j = 0 ; j < p ; j++ )
? ? {
? ? ? ? if( (a * j)%p == 1 )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? interver = j;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? }
?
? ? return interver;
}