fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int exp(int a,int n,int mod){
  5.     if(n==0) return 1;
  6.     int r;
  7.     r=exp(a,int(n/2),mod);
  8.     r=(r*r)%mod;
  9.     if(n%2==1) r=(r*a)%mod;
  10.     return r;
  11. }
  12. bool witness(int a,int n){
  13.     int t=0;
  14.     int u=n-1;
  15.     while(u%2==0){
  16.         u/=2;
  17.         t++;
  18.     }
  19.     int x[t];
  20.     x[0]=exp(a,u,n);
  21.     for(int i=1; i<t; i++){
  22.         x[i]=(x[i-1]*x[i-1])%n;
  23.         if(x[i]==1 && x[i-1] != 1 && x[i-1] !=n-1) return true;
  24.         if(x[t-1]!=1) return true;
  25.         return false;
  26.  
  27.     }
  28. }
  29. int main(){
  30.     int ans=0;
  31.     for(int i=1; i<57; i++){
  32.         if(witness(i,57)) ans++;
  33.     }
  34.     cout<<ans<<endl;
  35. }
  36.  
Success #stdin #stdout 0s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
56
https://ideone.com/E5vlsh
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!