中北大学ACM 5/12 T6 CSY的幸福

分手后的思念是犯贱 2021-12-14 14:47 302阅读 0赞

题面：

给出一个整数N，求有4^N个因数的最小整数，结果对998244353取余，找到这个数字就能让CSY获得幸福。(N<=100000)

--------------------

(原题并不是CSY)去打AKM比赛，6道水题，2道蓝题，2道紫题，这道题大概在紫题水平？（我太菜了）

平常我AKM压得贼（bu）稳【雾】，考试翻车加爆炸只打出来4道（丢人）

看一眼题，第一个思路是质因数分解，因子个数即为每个质数的指数+1。

首先把**尽可能多的**质数塞进一个小根堆里,

4^N可以化为2^2N,递推做法,每次为了让N走一位,把堆顶取出,让答案乘以这个数,

然后把取出的数乘以他本身塞回小根堆里.

这样做的原因是,设ans=p1^c1 + p2^c2 + p3^c3...pn^cn;

2^2N = (c1+1)(c2+1)(c3+1).....(cn+1)

因为左边的2^2N我们大概可以猜到右边是（1+1）（3+1）（7+1）（15+1）之类的形式

2^1 =(1+1) 所以我们选最小质因子的2

2^2=（1+1）（1+1）=（3+1） （3+1）意味着乘以2^2，（1+1）（1+1）意味着乘以3, 3更小所以选3.

2^3= （1+1）(1+1)(1+1) = (3+1)(1+1) 依序是乘以5或者乘以2^2，后者更小所以是（1+1）（3+1）

模拟就模拟到这

上面的那个堆存的就是为了让n走一位可以乘以哪些数，乘完了往回塞乘以它本身的本质是让存进去的数的指数为2的次方

（1+1）变成（3+1）乘以的就是2^2，（3+1）变成（7+1）乘以的是2^4

正确性得证。

维护优先队列的时复为N logN，复杂度正确。

考试的时候脑子一抽质数筛只筛到200000，前面的质数指数过大爆掉LONGLONG，到死没有发现BUG。

（结论就是CSY无法获得幸福）

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define p 998244353
    
    using namespace std ;
    
    long long pri[500010],psz,tag[500010],n;
    void prime(){
        for(int i=2;i<=500000;i++) { //报血海深仇 
            if(!tag[i]) {
                pri[++psz]=i;
                tag[i]=i;
            }
            for(int j=1;j<=psz;j++) {
                if(pri[j] > tag[i] || pri[j] > n/i) break;
                tag[i * pri[j]] = pri[j];
            }
        } 
    }
    
    priority_queue<long long> q;//我忘记小根堆怎么写了，存个负数水一下 = = 
    
    int main(){
        cin>>n;
        n*=2;
        prime();
        for(int i=1;i<=psz;i++){
            q.push(-pri[i]);
        }
        long long ans=1;
        for(int i=1;i<=n;i++){
            long long now=q.top();
            now*=-1;
            q.pop();
            ans*=now;
            ans%=p;
            q.push(-(now*now));
        }
        cout<<ans<<endl;
        return 0;
    }

TAG：SIN\_XIII ⑨

转载于:https://www.cnblogs.com/SINXIII/p/10857494.html