Submission #33867609

---

Source Code Expand

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

typedef long long ll;
typedef __int128 lll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read


ll quick_p(ll b, ll p,ll mod){
  ll r = 1;
  while(p){
    if(p%2)(r*=b)%=mod;
    (b*=b)%=mod;
    assert(r>0);
    assert(b>0);
    p/=2;
  }
  return r%mod;
}

bool is_prime_32(ll v){
  if(v == 2)return true;
  if(v < 2)return false;
  if(v%2 == 0)return false;
  ll test_g[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  ll startp = v-1;
  while(startp%2 == 0)startp>>=1;
  rep(i,0,7){
    ll p = startp;
    ll base = test_g[i];
    // don't break may cause 4033 bug
    if(base % v == 0)continue;
    bool find = false;
    ll r = quick_p(base,p,v);
    while(p != v-1){
      if(r == v-1){
        find = true;
        break;
      }
      // -1 开始的序列, 或全1序列
      if(r == 1){
        if(p == startp){
          find = true;
          break;
        }
        return false;
      }
      p*=2;
      (r*=r)%=v;
    }
    if(!find){
      return false;
    }
  }
  return true;
}

ll my_sqrt(ll v){
  assert(v > 1);
  ll l = 1;
  ll r = v; // care overflow
  ll ret = 1;
  while(l < r){
    ll m = (l+r)/2;
    ll m2 = m*m;
    if(m2 == v) return m;
    if(m2 < v) {
      ret = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return ret;
}

ll randint(ll low,ll hi){
  return low + (rand() % static_cast<int>(hi - low + 1));
}

ll Pollard_Rho(ll N) { // 返回一个> 1的因数
  assert(N > 1);
  if (N == 4) return 2;
  ll ret = my_sqrt(N); // 质数平方 效率低 提前判断
  if(ret * ret == N) return ret;
  while(true) {
    ll c = randint(1, N - 1); // 生成随机的c
    auto f = [=](ll x) { return ((lll)x * x + c) % N; }; // ll 表示__int128，防溢出
    ll t = 0, r = 0; // 初始两个相同
    do{
      t = f(t); // 1倍速度
      r = f(f(r)); // 2倍速度
      ll d = gcd(abs(t - r), N);
      if (d > 1 && d < N) return d;
    }while (t != r);
  }
}

// 分解x为质因数, sorted, {prime,power}
vector<pair<ll,int> > fenjie(ll x) {
  vector<int> res = {};
  deque <ll> arr = {x};
  while(arr.size()){
    ll v = arr.front();
    arr.pop_front();
    if(v == 1) continue;
    if(is_prime_32(v)) {
      res.pb(v);
      continue;
    }
    ll divisor = Pollard_Rho(v);
    arr.push_back(divisor);
    arr.push_back(v/divisor);
  }
  sort(res.begin(),res.end());
  vector<pair<ll,int> > ret;
  rep(i,0,res.size()){
    if(i == 0|| res[i] != res[i-1]) ret.push_back({res[i], 1});
    else ret.back().second++;
  }
  return ret;
}

ll phi(ll n){
  auto primes = fenjie(n);
  // printf("%lld =",n);
  // for(auto [v,pwr]:primes) printf("[%lld %d]",v,pwr);
  // printf("\n");
  ll ret = n;
  for(auto [v,pwr]:primes) ret = (ret/v)*(v-1);
  return ret;
}

// ------ lib ------

int n ;

// test pwr 10^p = k 9v + 1,  10^p % 9v == 1
bool testPwr(ll p){
  return quick_p(10, p, 9 * n) == 1;
}

void dfs(int idx, vector<pair<ll,int>> primes, ll mul, ll & ans){
  if(idx == (int)primes.size()){
    if(testPwr(mul)) ans = min(ans,mul);
    return ;
  }
  rep(pwr,0,primes[idx].second+1){
    dfs(idx+1,primes,mul,ans);
    mul *= primes[idx].first;
  }
}

void w(){
  n = read();
  if(n % 4 == 0 || n % 5 == 0){
    printf("-1\n");
    return ;
  }
  if(n % 2 == 0) n /= 2;
  ll phin = n % 3 == 0 ? phi(9*n) : phi(n);
  if(phin == 1){
    printf("1\n");
    return ;
  }
  // printf("test %lld: %d\n",phin,(int)testPwr(phin,n));
  auto primes = fenjie(phin);
  ll ans = phin;
  dfs(0, primes, 1, ans);
  printf("%lld\n",ans);
}


int main(){
  int t = read();
  while(t--) w();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result