結果

問題 No.2798 Multiple Chain
ユーザー Shreyan RayShreyan Ray
提出日時 2024-06-28 21:45:00
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 7,204 bytes
コンパイル時間 2,745 ms
コンパイル使用メモリ 226,872 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 21:45:05
合計ジャッジ時間 4,628 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
5,248 KB
testcase_01 AC 10 ms
5,376 KB
testcase_02 AC 9 ms
5,376 KB
testcase_03 AC 9 ms
5,376 KB
testcase_04 AC 9 ms
5,376 KB
testcase_05 AC 9 ms
5,376 KB
testcase_06 AC 9 ms
5,376 KB
testcase_07 AC 10 ms
5,376 KB
testcase_08 AC 10 ms
5,376 KB
testcase_09 AC 9 ms
5,376 KB
testcase_10 AC 9 ms
5,376 KB
testcase_11 AC 10 ms
5,376 KB
testcase_12 AC 10 ms
5,376 KB
testcase_13 AC 9 ms
5,376 KB
testcase_14 AC 9 ms
5,376 KB
testcase_15 AC 9 ms
5,376 KB
testcase_16 AC 9 ms
5,376 KB
testcase_17 AC 10 ms
5,376 KB
testcase_18 AC 9 ms
5,376 KB
testcase_19 AC 9 ms
5,376 KB
testcase_20 AC 9 ms
5,376 KB
testcase_21 AC 9 ms
5,376 KB
testcase_22 AC 9 ms
5,376 KB
testcase_23 AC 9 ms
5,376 KB
testcase_24 AC 9 ms
5,376 KB
testcase_25 AC 9 ms
5,376 KB
testcase_26 AC 9 ms
5,376 KB
testcase_27 AC 9 ms
5,376 KB
testcase_28 AC 10 ms
5,376 KB
testcase_29 AC 9 ms
5,376 KB
testcase_30 AC 9 ms
5,376 KB
testcase_31 AC 10 ms
5,376 KB
testcase_32 AC 9 ms
5,376 KB
testcase_33 AC 10 ms
5,376 KB
testcase_34 AC 10 ms
5,376 KB
testcase_35 AC 9 ms
5,376 KB
testcase_36 AC 10 ms
5,376 KB
testcase_37 AC 10 ms
5,376 KB
testcase_38 AC 9 ms
5,376 KB
testcase_39 AC 10 ms
5,376 KB
testcase_40 AC 10 ms
5,376 KB
testcase_41 AC 10 ms
5,376 KB
testcase_42 AC 10 ms
5,376 KB
testcase_43 AC 10 ms
5,376 KB
testcase_44 AC 9 ms
5,376 KB
testcase_45 AC 10 ms
5,376 KB
testcase_46 AC 10 ms
5,376 KB
testcase_47 AC 10 ms
5,376 KB
testcase_48 AC 9 ms
5,376 KB
testcase_49 AC 9 ms
5,376 KB
testcase_50 AC 10 ms
5,376 KB
testcase_51 AC 9 ms
5,376 KB
testcase_52 AC 9 ms
5,376 KB
testcase_53 AC 9 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0