test/aoj/2720.test.cpp

• View this file on GitHub
• Last update: 2020-10-24 13:53:02+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2720

Depends on

• math/carmichael.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2720

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../math/carmichael.cpp"
#undef call_from_test

// x^n mod m
template<typename T>
T mpow(T x,T n,T m){
  T r=1;
  x%=m;
  while(n){
    if(n&1) r=r*x%m;
    x=x*x%m;
    n>>=1;
  }
  return r;
}

signed main(){
  using ll = long long;
  ll n;
  cin>>n;
  if(n==2){
    cout<<1<<endl;
    return 0;
  }
  for(ll i=2;i*i<=n;i++){
    if(n%(i*i)==0){
      cout<<-1<<endl;
      return 0;
    }
  }

  ll a=carmichael_lambda(n);
  ll b=carmichael_lambda(a);
  assert(n!=1);
  assert(a!=1);
  assert(b!=0);
  {
    ll x=mpow(n,b,a)!=1;
    ll y=__gcd(n%a,a)!=1;
    assert(x==y);
  }
  if(mpow(n,b,a)!=1){
    assert(n%a!=1);
    cout<<-1<<endl;
    return 0;
  }

  if(n%a==1) b=1;
  for(ll i=2;i*i<=b;i++){
    if(b%i!=0) continue;
    while(b%i==0){
      if(mpow(n,b/i,a)==1) b/=i;
      else break;
    }
    ll j=b/i;
    if(j==1) continue;
    while(b%j==0){
      if(mpow(n,b/j,a)==1) b/=j;
      else break;
    }
  }
  cout<<b<<endl;
  return 0;
}

#line 1 "test/aoj/2720.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2720

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "math/carmichael.cpp"

#line 3 "math/carmichael.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// min m s.t. a^m = 1 mod n (a, n are coprime)
template<typename T>
T carmichael_lambda(T n){
  T res=1;
  if(n%8==0) n/=2;
  for(int i=2;i*i<=n;i++){
    if(n%i==0){
      T tmp=i-1;
      for(n/=i;n%i==0;n/=i) tmp*=i;
      res=lcm(res,tmp);
    }
  }
  if(n!=1) res=lcm(res,n-1);
  return res;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/2720.test.cpp"
#undef call_from_test

// x^n mod m
template<typename T>
T mpow(T x,T n,T m){
  T r=1;
  x%=m;
  while(n){
    if(n&1) r=r*x%m;
    x=x*x%m;
    n>>=1;
  }
  return r;
}

signed main(){
  using ll = long long;
  ll n;
  cin>>n;
  if(n==2){
    cout<<1<<endl;
    return 0;
  }
  for(ll i=2;i*i<=n;i++){
    if(n%(i*i)==0){
      cout<<-1<<endl;
      return 0;
    }
  }

  ll a=carmichael_lambda(n);
  ll b=carmichael_lambda(a);
  assert(n!=1);
  assert(a!=1);
  assert(b!=0);
  {
    ll x=mpow(n,b,a)!=1;
    ll y=__gcd(n%a,a)!=1;
    assert(x==y);
  }
  if(mpow(n,b,a)!=1){
    assert(n%a!=1);
    cout<<-1<<endl;
    return 0;
  }

  if(n%a==1) b=1;
  for(ll i=2;i*i<=b;i++){
    if(b%i!=0) continue;
    while(b%i==0){
      if(mpow(n,b/i,a)==1) b/=i;
      else break;
    }
    ll j=b/i;
    if(j==1) continue;
    while(b%j==0){
      if(mpow(n,b/j,a)==1) b/=j;
      else break;
    }
  }
  cout<<b<<endl;
  return 0;
}

Back to top page