这是本蒟蒻第一篇题解

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

先讲思路

题目说 $2\leqslant n\leqslant 10¹²$ 所以肯定要开 long long
题目中提到了因子，肯定要先分解质因数（标准），整合一波后是第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个

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

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

这道题就是上面五步

然后直接上代码

CPP

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

无注释版本

CPP

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

没看懂,那就再看

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

文章操作

这是本蒟蒻第一篇题解

相关推荐

评论

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