結果
| 問題 |
No.2798 Multiple Chain
|
| コンテスト | |
| ユーザー |
 Shreyan Ray
|
| 提出日時 | 2024-06-28 21:45:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 36 ms / 2,000 ms |
| コード長 | 7,204 bytes |
| コンパイル時間 | 2,553 ms |
| コンパイル使用メモリ | 218,516 KB |
| 最終ジャッジ日時 | 2025-02-22 01:01:09 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 51 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
uint64_t Number(uint64_t a,uint64_t b){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
return (a+rng()%(b-a+1));
}
uint64_t stein(uint64_t x,uint64_t y){
if(x==y) return x;
uint64_t a=y-x;
uint64_t b=x-y;
int n=__builtin_ctzll(b);
uint64_t s=(x<y?a:b);
uint64_t t=(x<y?x:y);
return stein(s>>n,t);
}
uint64_t fastGCD(uint64_t x,uint64_t y){
if(x==0) return y;
if(y==0) return x;
int n=__builtin_ctzll(x);
int m=__builtin_ctzll(y);
return (stein(x>>n,y>>m)<<(n<m?n:m));
}
uint64_t limit=2147483648;
vector<int> small={2,3,5,7};
vector<int> large={2,3,5,7,11,13,17,19,23};
uint64_t exp(uint64_t x,uint64_t y,uint64_t m){
uint64_t res=1;
while(y){
if(y&1) res=((__uint128_t)res*x)%m;
x=((__uint128_t)x*x)%m;
y>>=1;
}
return res;
}
bool isComposite(uint64_t a,uint64_t d,uint64_t n,uint64_t s){
uint64_t x=exp(a,d,n);
if(x==1) return false;
while(s--){
if(x==n-1) return false;
x=((__uint128_t)x*x)%n;
}
return true;
}
bool isPrime(uint64_t n){
if(n==1) return false;
vector<int> bases=(n<limit?small:large);
if(find(bases.begin(),bases.end(),n)!=bases.end()) return true;
for(int p:bases) if(n%p==0) return false;
uint64_t s=__builtin_ctzll(n-1);
uint64_t d=(n-1)>>s;
for(int base:bases){
if(isComposite(base,d,n,s)) return false;
}
return true;
}
class Montgomery{
uint64_t m;
uint64_t r;
public:
Montgomery(uint64_t n):m(n),r(n){
for(int i=0;i<5;i++){
r*=2-m*r;
}
}
uint64_t fma(uint64_t a,uint64_t b,uint64_t c) const{
__uint128_t d=__uint128_t(a)*b;
uint64_t e=c+m+(d>>64);
uint64_t f=uint64_t(d)*r;
uint64_t g=(__uint128_t(f)*m)>>64;
return (e-g);
}
uint64_t mul(uint64_t a,uint64_t b) const{
return fma(a,b,0);
}
};
// uint64_t pollard_rho( uint64_t n ) {
// if( n % 2 == 0 ) { return 2; }
// const Montgomery m( n );
// constexpr uint64_t C1 = 1;
// constexpr uint64_t C2 = 2;
// constexpr uint64_t M = 512;
// uint64_t Z1 = 1;
// uint64_t Z2 = 2;
// retry:
// uint64_t z1 = Z1;
// uint64_t z2 = Z2;
// for( size_t k = M; ; k *= 2 ) {
// const uint64_t x1 = z1 + n;
// const uint64_t x2 = z2 + n;
// for( size_t j = 0; j < k; j += M ) {
// const uint64_t y1 = z1;
// const uint64_t y2 = z2;
// uint64_t q1 = 1;
// uint64_t q2 = 2;
// z1 = m.fma( z1, z1, C1 );
// z2 = m.fma( z2, z2, C2 );
// for( size_t i = 0; i < M; ++i ) {
// const uint64_t t1 = x1 - z1;
// const uint64_t t2 = x2 - z2;
// z1 = m.fma( z1, z1, C1 );
// z2 = m.fma( z2, z2, C2 );
// q1 = m.mul( q1, t1 );
// q2 = m.mul( q2, t2 );
// }
// q1 = m.mul( q1, x1 - z1 );
// q2 = m.mul( q2, x2 - z2 );
// const uint64_t q3 = m.mul( q1, q2 );
// const uint64_t g3 = fastGCD( n, q3 );
// if( g3 == 1 ) { continue; }
// if( g3 != n ) { return g3; }
// const uint64_t g1 = fastGCD( n, q1 );
// const uint64_t g2 = fastGCD( n, q2 );
// const uint64_t C = g1 != 1 ? C1 : C2;
// const uint64_t x = g1 != 1 ? x1 : x2;
// uint64_t z = g1 != 1 ? y1 : y2;
// uint64_t g = g1 != 1 ? g1 : g2;
// if( g == n ) {
// do {
// z = m.fma( z, z, C );
// g = fastGCD( n, x - z );
// } while( g == 1 );
// }
// if( g != n ) {
// return g;
// }
// Z1 += 2;
// Z2 += 2;
// goto retry;
// }
// }
// }
uint64_t rho(uint64_t n){
if(n%2==0) return 2;
Montgomery m(n);
uint64_t c1=1;
uint64_t c2=2;
uint64_t M=512;
uint64_t w1=1;
uint64_t w2=2;
retry:
uint64_t z1=w1;
uint64_t z2=w2;
for(uint64_t k=M;;k<<=1){
uint64_t x1=z1+n;
uint64_t x2=z2+n;
for(uint64_t j=0;j<k;j+=M){
uint64_t y1=z1;
uint64_t y2=z2;
uint64_t q1=1;
uint64_t q2=2;
z1=m.fma(z1,z1,c1);
z2=m.fma(z2,z2,c2);
for(uint64_t i=0;i<M;i++){
uint64_t t1=x1-z1;
uint64_t t2=x2-z2;
z1=m.fma(z1,z1,c1);
z2=m.fma(z2,z2,c2);
q1=m.mul(q1,t1);
q2=m.mul(q2,t2);
}
q1=m.mul(q1,x1-z1);
q2=m.mul(q2,x2-z2);
uint64_t q3=m.mul(q1,q2);
uint64_t g3=fastGCD(n,q3);
if(g3==1) continue;
if(g3!=n) return g3;
uint64_t g1=fastGCD(n,q1);
uint64_t g2=fastGCD(n,q2);
uint64_t c=(g1!=1?c1:c2);
uint64_t x=(g1!=1?x1:x2);
uint64_t z=(g1!=1?y1:y2);
uint64_t g=(g1!=1?g1:g2);
if(g==n){
do{
z=m.fma(z,z,c);
g=fastGCD(n,x-z);
}while(g==1);
}
if(g!=n) return g;
w1+=2;
w2+=2;
goto retry;
}
}
}
void factorize(uint64_t n,vector<uint64_t> &res){
if(n<=1) return;
if(isPrime(n)){
res.push_back(n);
return;
}
uint64_t p=rho(n);
factorize(p,res);
factorize(n/p,res);
}
vector<uint64_t> solve(uint64_t n){
vector<uint64_t> res;
factorize(n,res);
sort(res.begin(),res.end());
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
uint64_t n;
cin>>n;
vector<uint64_t> factors=solve(n);
// cout<<factors.size()<<" \n"[factors.empty()];
// for(int i=0;i<factors.size();i++){
// cout<<factors[i]<<" \n"[i+1==factors.size()];
// }
#define int long long
map <int, int> m;
for (auto x : factors){
m[x]++;
}
// dp[sum][last] = ways
vector<vector<int>> dp(65, vector<int>(65, 0));
vector<int> tot(65, 0);
for (int i = 1; i <= 64; i++){
dp[i][i] = 1;
tot[i] = 1;
}
for (int i = 1; i <= 64; i++){
vector<vector<int>> ndp(65, vector<int>(65, 0));
for (int s1 = 1; s1 <= 64; s1++){
for (int last = 1; last <= s1; last++){
for (int nx = last; nx <= 64; nx++){
if (nx + s1 <= 64){
ndp[nx + s1][nx] += dp[s1][last];
}
}
}
}
dp = ndp;
for (int s1 = 1; s1 <= 64; s1++){
for (int last = 1; last <= s1; last++){
tot[s1] += dp[s1][last];
}
}
}
int ans = 1;
for (auto [x, y] : m){
ans *= tot[y];
}
cout << ans << "\n";
return 0;
}