题解：B4070 [GESP202412 五级] 奇妙数字

· · 题解

这是本蒟蒻第一篇题解

（本题还是有难度滴,但不多）

先讲思路

  1. 题目说2\leqslant n\leqslant 10¹²所以肯定要开 long long

  2. 题目中提到了因子，肯定要先分解质因数（标准），整合一波后是第3步

  3. 每个因子都要进行利用最大化，比如：

10^1¹²\implies 10^1\times10^2\times10^3\times10^4\times10^2

然后，读了题目的人就知道10^1¹²的包含最多奇妙数字有4个

比如： 2^0²\times3^7\implies 10^1\times3^1\times3^2\times3^3 \times2^1\times3^1

那么2^0²\times3^7的包含最多奇妙数字有4个

  1. 就像刚才那样 找 每个因子的指数 包含 多少个 完整的 斐波那契数列

5.将第四步的所有成果累加

这道题就是上面五步

然后直接上代码

#include <bits/stdc++.h>
using namespace std;
#define int long long//方便打字，懒得写long long 
const int N=1e6+10;//保险一点 
int n;
//结构体整合因子和指数 
struct node{
    int a;//因子 
    int ans;//对应指数 
}factor[N]; 
int cnt; 
void check(int n){
    int t=0;//记录指数 
    for(int i=2;i*i<=n;i++){//分解质因数+整合保存 
        t=0;
        if(n%i==0){//分解质因数1 
            while(n%i==0){ //分解质因数2 
                t++; 
                n/=i;//分解质因数3
            }
            factor[++cnt].a=i; //保存 
            factor[cnt].ans=t;  //  这里不能++cnt 
        }
    }   
    if(n>1){//正常操作 
        factor[++cnt].a=n;
        factor[cnt].ans=1;
    }
}
int prime(int x){
    int cnt=0,t=0;
    while(true){//很笨的一种找斐波那契的方法(可以自个儿优化) 
        cnt++;
        if(x-cnt>=0){
            t++;
            x-=cnt; 
        } 
        else break;
    }
    return t;
}
signed main(){
    cin>>n;
    check(n);
    int num=0;
    for(int i=1;i<=cnt;i++) num+=prime(factor[i].ans);//不多说了 
    cout<<num;
    return 0;
}

无注释版本

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n;
struct node{
    int a;
    int ans;
}factor[N]; 
int cnt;
void check(int n){
    int t=0;
    for(int i=2;i*i<=n;i++){
        t=0;
        if(n%i==0){
            while(n%i==0){
                t++;
                n/=i;
            }
            factor[++cnt].a=i;
            factor[cnt].ans=t;      
        }
    }   
    if(n>1){
        factor[++cnt].a=n;
        factor[cnt].ans=1;
    }
}
int prime(int x){
    int cnt=0,t=0;
    while(true){
        cnt++;
        if(x-cnt>=0){
            t++;
            x-=cnt; 
        } 
        else break;
    }
    return t;
}
signed main(){
    cin>>n;
    check(n);
    int num=0;
    for(int i=1;i<=cnt;i++) num+=prime(factor[i].ans);
    cout<<num;
    return 0;
}

没看懂,那就再看