Where_Free

  1 #include <iostream>
  2 #include <map>
  3 #include <time.h>
  4 using namespace std;
  5 #define ll long long
  6 /**
  7 Miller_Rabin 算法進行素數測試
  8 快速判斷一個<2^63的數是不是素數,主要是根據費馬小定理
  9 */
 10 //#define ll __int128
 11 const int S=8; ///隨機化算法判定次數
 12 ll MOD;
 13 ///計算ret=(a*b)%c  a,b,c<2^63
 14 ll mult_mod(ll a,ll b,ll c)
 15 {
 16     a%=c;
 17     b%=c;
 18     ll ret=0;
 19     ll temp=a;
 20     while(b)
 21     {
 22         if(b&1)
 23         {
 24             ret+=temp;
 25             if(ret>c)
 26                 ret-=c;//直接取模慢很多
 27         }
 28         temp<<=1;
 29         if(temp>c)
 30             temp-=c;
 31         b>>=1;
 32     }
 33     return ret;
 34 }
 35 
 36 ///計算ret=(a^n)%mod
 37 ll pow_mod(ll a,ll n,ll mod)
 38 {
 39     ll ret=1;
 40     ll temp=a%mod;
 41     while(n)
 42     {
 43         if(n&1)
 44             ret=mult_mod(ret,temp,mod);
 45         temp=mult_mod(temp,temp,mod);
 46         n>>=1;
 47     }
 48     return ret;
 49 }
 50 
 51 ///通過費馬小定理 a^(n-1)=1(mod n)來判斷n是否為素數
 52 ///中間使用了二次判斷,令n-1=x*2^t
 53 ///是合數返回true，不一定是合數返回false
 54 bool check(ll a,ll n,ll x,ll t)
 55 {
 56     ll ret=pow_mod(a,x,n);
 57     ll last=ret;//記錄上一次的x
 58     for(int i=1;i<=t;i++)
 59     {
 60         ret=mult_mod(ret,ret,n);
 61         if(ret==1&&last!=1&&last!=n-1)
 62             return true;//二次判斷為是合數
 63         last=ret;
 64     }
 65     if(ret!=1)
 66         return true;//是合數,費馬小定理
 67     return false;
 68 }
 69 
 70 
 71 ///Miller_Rabbin算法
 72 ///是素數返回true(可能是偽素數)，否則返回false
 73 bool Miller_Rabbin(ll n)
 74 {
 75     if(n<2) return false;
 76     if(n==2) return true;
 77     if((n&1)==0) return false;//偶數
 78     ll x=n-1;
 79     ll t=0;
 80     while((x&1)==0)
 81     {
 82         x>>=1;
 83         t++;
 84     }
 85     srand(time(NULL));
 86     for(int i=0;i<S;i++)
 87     {
 88         ll a=rand()%(n-1)+1; // 生成隨機數 0<a<=n-1  去試試
 89         if(check(a,n,x,t))
 90             return false;
 91     }
 92     return true;
 93 }
 94 int main(){
 95     ll n,p,q;
 96     cin>>n;
 97     for(int i=0;i<2000000000;i++){
 98         if(Miller_Rabbin(i)){
 99             p=n/i;
100             if(Miller_Rabbin(p)&&i*p==n){
101                 cout<<p<<" "<<i<<'\n';
102                 break;
103             }
104         }
105     }
106 }

 1 #include <iostream>
 2 using namespace std;
 3 #define ll long long
 4 ll exgcd(ll a,ll b,ll &x,ll &y){
 5     
 6     if(a==0&&b==0) return -1;
 7     if(b==0){
 8         x=1,y=0;
 9         return a;
10     }
11     ll d=exgcd(b,a%b,y,x);
12     //cout<<a<<" "<<b<<'\n';
13     y-=a/b*x;
14     return d;
15 }
16 ll poww(ll a,ll b,ll c){  //快速冪取模
17     ll ans(1),base=a%c;
18     //a=a%c;
19     while(b){
20         if(b&1) ans=(ans*base)%c;
21         base=base*base%c;
22         b>>=1;
23     }
24     return ans;
25 }
26 
27 int main(){
28     int flag(0);
29     ll p,q,ou,ed,n,e(17),x(1),y(1),num1,ans,s;
30     cin>>flag;
31     if(flag==1){
32         cout<<"依次輸入 p q 與 e:";
33         cin>>p>>q;
34         n=p*q;
35         ou=(p-1)*(q-1);
36         cin>>e;
37         num1=exgcd(e,ou,x,y);
38         //y=y+e/ou*x;
39         if(x<=0)x=(x+ou)%ou;
40         //x=(x+e)%e;
41         cout<<"N值："<<n<<'\n';
42         cout<<"公鑰："<<e<<'\n';
43         cout<<"密鑰："<<x<<'\n';
44         return 0;
45     }
46     if(flag==2){
47         cin>>s>>e>>n;
48         ans=poww(s,e,n);
49         cout<<ans<<'\n';
50     }
51 }

 1 def poww(a,n,mod):
 2     ret=1
 3     tmp=a%mod
 4     while(n>0):
 5         if(n%2!=0):
 6             ret=(ret*tmp)%mod
 7         tmp=tmp*tmp%mod
 8         n>>=1
 9     return ret
10 s1=e=n=1.0
11 n=int(input())
12 e=int(input())
13 while(True):
14      s1=int(input())
15      ans=poww(s1,e,n)
16      print(ans)