結果

問題 No.3093 Please GCD
ユーザー silv723silv723
提出日時 2022-04-01 22:54:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,000 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 206,236 KB
実行使用メモリ 40,280 KB
平均クエリ数 23.47
最終ジャッジ日時 2024-11-20 11:19:21
合計ジャッジ時間 76,675 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
25,092 KB
testcase_01 AC 25 ms
25,220 KB
testcase_02 AC 30 ms
24,580 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 54 ms
25,220 KB
testcase_11 AC 44 ms
24,580 KB
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 AC 66 ms
24,836 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
権限があれば一括ダウンロードができます

ソースコード

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(){
	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