摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

http://www.tcgs.tc.edu.tw/blog/index.php?op=ViewArticle&articleId=232&blogId=2
補完計畫↑

( a^m - b^m , a^n - b^n )
=( a^m - b^m , a^n - b^n - (a^m - b^m)*a^(n-m) )
=( a^m - b^m , - b^n + b^m*a^(n-m) )
=( a^m - b^m , b^m*a^(n-m) - b^(n-m)*b^m )
=( a^m - b^m , b^m*(a^(n-m) - b^(n-m))
=( a^m - b^m , a^(n-m) - b^(n-m) ) 發現到n跟m在做輾轉的步驟
= ... = a^(n,m) - b^(n,m)

/***********************************************************/

#include<stdio.h>  
#include<stdlib.h>  
int gcd(int a,int b)              
 {              
  int temp;              
  while(a%b)                    
   {                    
    temp=a;                    
    a=b;                    
    b=temp%b;                               
   }              
   return b;              
 }
int pow(int a, int n, int p)
{
    int b,temp=1;
    for (b=0;b<n;b++)
        temp=(temp*a)%p;
    return temp;
}
main()  
{  
 int a,b,m,n,p;
 while(scanf("%d %d %d %d %d",&a,&b,&m,&n,&p)==5)   
  {  
   int gg=gcd(m,n);
   a=pow(a,gg,p);
   b=pow(b,gg,p);
   printf("%d\n",(p+a-b)%p);
  }    
 return 0;  
}