結果
問題 | No.1611 Minimum Multiple with Double Divisors |
ユーザー |
![]() |
提出日時 | 2021-07-21 21:35:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,680 ms / 2,000 ms |
コード長 | 3,464 bytes |
コンパイル時間 | 3,360 ms |
コンパイル使用メモリ | 196,828 KB |
最終ジャッジ日時 | 2025-01-23 03:35:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; ll powmod(__int128_t a, ll k, ll m){ __int128_t ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=m; } k>>=1; ap=ap*ap%m; } return ans; } bool is_prime(ll n){ if(n<=1 || !(n&1)) return (n==2); ll d=n-1; int k=0; while(!(d&1)){ d>>=1; k++; } vector<ll> va{2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // http://miller-rabin.appspot.com/ for(auto aa:va){ ll a=aa%n; if(a==0) continue; bool comp=1; ll ap=powmod(a, d, n); if(ap==1 || ap==n-1) continue; for(int r=1; r<k; r++){ ap=(__int128_t)ap*ap%n; if(ap==n-1){ comp=0; break; } } if(comp) return false; } return true; } ll gcd(ll a, ll b){ if(a==0) return b; if(b==0) return a; if(a<0) a=-a; if(b<0) b=-b; const int s=__builtin_ctzll(a|b); a>>=__builtin_ctzll(a); while(b){ b>>=__builtin_ctzll(b); if(a>b) swap(a, b); b-=a; } return a<<s; } ll rho(ll n, ll& c){ if(!(n&1)) return 2; while(1){ ll x=2, y=2, d=1; while(d==1){ x=((__int128_t)x*x+c)%n; y=((__int128_t)y*y%n+c)%n; y=((__int128_t)y*y%n+c)%n; d=gcd(abs(x-y), n); } if(d==n){ c++; continue; } return d; } } vector<pair<ll, int>> factorize(ll n){ if(n<=1){ vector<pair<ll, int>> ret; return ret; } map<ll, int> mp; vector<ll> v(1, n); ll c=1; while(!v.empty()){ ll x=v.back(); v.pop_back(); if(is_prime(x)){ mp[x]++; continue; } ll p=rho(x, c); v.push_back(p); v.push_back(x/p); } vector<pair<ll, int>> ret; for(auto p:mp) ret.push_back(p); return ret; } const int MAX=1000010; bitset<MAX> isprime; void sieve(){ for(int i=3; i<MAX; i++, i++) isprime[i]=1; isprime[2]=1; for(int i=3; i<MAX; i++){ if(isprime[i]){ for(int j=(i<<1); j<MAX; j+=i) isprime[j]=0; } } } int main() { int t; cin>>t; sieve(); map<ll, int> mp1[50]; for(int i=2; i<50; i++){ for(int j=2; j<50; j++){ if(!isprime[j]) continue; int x=i; while(x%j==0){ x/=j; mp1[i][j]++; } } } while(t--){ ll x; cin>>x; if(x%2!=0){ cout<<2*x<<endl; continue; } auto v=factorize(x); map<ll, int> mp; for(auto p:v) mp[p.first]=p.second; ll c=1; for(auto p:v) c*=(p.second+1); for(int i=2; ; i++){ if(isprime[i] && x%i!=0){ cout<<i*x<<endl; break; } ll c1=c; for(auto q:mp1[i]){ c1/=(mp[q.first]+1); mp[q.first]+=q.second; c1*=(mp[q.first]+1); } if(c1==c*2){ cout<<i*x<<endl; break; } for(auto q:mp1[i]){ mp[q.first]-=q.second; } } } return 0; }