結果

問題 No.8093 Please GCD
ユーザー silv723
提出日時 2022-04-01 22:58:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,056 bytes
コンパイル時間 2,216 ms
コンパイル使用メモリ 199,696 KB
最終ジャッジ日時 2025-01-28 14:20:27
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll mpow(ll n,ll k,ll m){
    ll ret=1;
    n%=m;
    while(k>0){
        if(k&1)ret*=n;
        n*=n;
        k>>=1;
        ret%=m;
        n%=m;
    }
    return ret;
}
bool miller_rabin(ll n){
    if(n==2) return true;
    if(n==1) return false;
    if(n%2==0) return false;
    ll m=n-1;
    ll s=0;
    ll d=0;
    while(m%2==0){
        s++;
        m/=2;
        d=m;
    }
    vector<ll> primecheck={2,325,9375,28178,450775,9780504,1795265022};
    for(int i=0;i<7;i++){
        if(n<=primecheck[i]) break;
        if(mpow(primecheck[i],d,n)!=1){
            ll cnt=d;
            ll y=mpow(primecheck[i],cnt,n);
            while(cnt!=n-1&&y!=1&&y!=n-1){
                y*=y;
                y%=n;
                cnt*=2;
            }
            if(y!=n-1&&cnt%2==0) return false;
        }
    }
    return true;
}
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
	ll n;
	cin>>n;
	vector<ll> v;
	for(ll i=2;i<=n;i++){
		if(miller_rabin(i)){
			v.push_back(i);
		}
	}
  ll now=0;
  ll cnt=1;
  vector<ll> ans;
	while(now<v.size()){
      if(cnt*v[now]<=n){
        cnt*=v[now];
        now++;
      }
      else{
        cout<<"? "<<cnt<<endl;
        ll k;
        cin>>k;
        if(miller_rabin(k)) ans.push_back(k);
        for(ll i=2;i*i<=k;i++){
          if(k%i==0){
            ans.push_back(i);
            ans.push_back(k/i);
          }
        }
        cnt=1;
      }
    }
  if(cnt!=1){
    cout<<"? "<<cnt<<endl;
        ll k;
        cin>>k;
        if(miller_rabin(k)) ans.push_back(k);
        for(ll i=2;i*i<=k;i++){
          if(k%i==0){
            ans.push_back(i);
            ans.push_back(k/i);
          }
        }
  }
  ll fans=1;
  for(int i=0;i<ans.size();i++){
    fans*=ans[i];
  }
  for(int i=0;i<ans.size();i++){
    if(ans[i]*fans>n) continue;
    ll x=ans[i];
    while(x<=n){
      x*=ans[i];
    }
    x/=ans[i];
    cout<<"? "<<x<<endl;
    ll z;
    cin>>z;
    fans*=z;
    fans/=ans[i];
  }
  cout<<"! "<<fans<<endl;
}
0