結果
問題 | No.3028 No.9999 |
ユーザー |
|
提出日時 | 2025-02-21 21:36:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 4,000 ms |
コード長 | 4,033 bytes |
コンパイル時間 | 7,645 ms |
コンパイル使用メモリ | 333,444 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-21 21:36:29 |
合計ジャッジ時間 | 8,195 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint = atcoder::static_modint<998244353>; // // using mint = atcoder::static_modint<1000000007>; using ld = long double; using ll = long long; #define mp(a,b) make_pair(a,b) #define rep(i,s,n) for(int i=s; i<(int)n; i++) const vector<int> dx{1,0,-1,0},dy{0,1,0,-1}; bool is_prime(ll x){ // miller rabin auto pow_mod=[&](__int128_t a,ll k,__int128_t mod){ __int128_t output=1; a%=mod; while(k){ if(k&1)output=(output*a)%mod; a=(a*a)%mod; k>>=1; } return output; }; if(x<=1)return false; vector<ll> test; if(x<4759123141)test={2,7,61}; else test={2,325,9375,28178,450775,9780504,1795265022}; ll K=x-1; while(!(K&1))K>>=1; for(ll a:test){ if(a>=x)return true; bool ok=false; ll k=K; __int128_t c=pow_mod(a,k,x); if(c==1)ok=true; else{ while(k<=x-1){ if(c==x-1){ ok=true; break; } c=c*c%x; k<<=1; } } if(!ok)return false; } return true; } vector<pair<ll,int>> factorize(ll n){ // Pollard's rho vector<pair<ll,int>> output; rep(i,2,100){ while(n%i==0){ output.push_back(mp(i,0)); while(n%i==0)n/=i,output.back().second++; } if(n==1)return output; } stack<ll> calc; random_device rd; mt19937 engine(rd()); vector<ll> P; calc.push(n); while(calc.size()){ n=calc.top();calc.pop(); while(!is_prime(n)){ __int128_t x=engine()%n,y=x; ll plus=engine()%n+1; int i=1; while(true){ x=(x*x+plus)%n; y=(y*y+plus)%n; y=(y*y+plus)%n; ll d=x-y;d=abs(d); ll g=gcd(d,n); if(g==1)i++; else if(g==n)break; else{ if(is_prime(g))P.push_back(g); else calc.push(g); n/=g; break; } } } P.push_back(n); } sort(P.begin(),P.end()); for(auto p:P){ if(output.size()==0 || output.back().first!=p)output.push_back(mp(p,1)); else output.back().second++; } return output; } vector<pair<ll,int>> multiplicative_group(ll p,int k){ // mod p^kの乗法群を巡回群に分解 vector<pair<ll,int>> output; if(p==2){ if(k==2)output.push_back(mp(2,1)); else if(k>=3){ output.push_back(mp(2,1)); output.push_back(mp(2,k-2)); } } else{ auto v=factorize(p-1); for(auto pk:v)output.push_back(pk); if(k>1)output.push_back(mp(p,k-1)); sort(output.begin(),output.end()); } return output; } vector<pair<ll,int>> multiplicative_group_decomposition(vector<pair<ll,int>> P){ // (p,k)=p^kの素因数分解の形をvectorで渡すと乗法群を巡回群に分解、sortして返すmultiplicative_group_decomposition(factorize(n))で動く vector<pair<ll,int>> output; for(auto [p,k]:P){ auto v=multiplicative_group(p,k); for(auto pk:v)output.push_back(pk); } sort(output.begin(),output.end()); return output; } int main(){ ll n;cin >> n; if(n==1){ cout << 1 << "\n"; return 0; } auto P=multiplicative_group_decomposition(factorize(n)); ll order=1; reverse(P.begin(),P.end()); ll last=-1; vector<ll> Q; for(auto [p,k]:P){ // cout << p << " " << k << "\n"; if(p!=last){ Q.push_back(p); rep(i,0,k)order*=p; last=p; } } // cout << order; for(auto p:Q){ while(order%p==0 && pow_mod(10,order/p,n)==1)order/=p; } cout << order << "\n"; }