E-rin和快速迭代
题目描述
rin最近喜欢上了数论。
然而数论实在太复杂了,她只能研究一些简单的问题。
这天,她在研究正整数因子个数的时候,想到了一个“快速迭代”算法。设 f(x)f(x)f(x)f(x)f(x)f(x)f(x)f(x)f(x) 为 xxxxxxxxx 的因子个数,将 fffffffff 迭代下去,rin猜想任意正整数最终都会变成 222222222 。
例如:f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2f(12)=6,f(6)=4,f(4)=3,f(3)=2 。
她希望你帮她验证一下。她会给你一个正整数 ,让你输出它在迭代过程中,第一次迭代成 222222222 的迭代次数。
输入描述:
一个正整数 nnnnnnnnn(3≤n≤10123≤n≤10123≤n≤10123≤n≤10123 \le n \le 10^{12}3≤n≤10123≤n≤10123≤n≤10123≤n≤1012)
输出描述:
一个正整数,为 nnnnnnnnn 迭代至 222222222 的次数。
示例1
12
4
*/
思路如下
暴力求解这一题,让我们求某个数的因子,我们就直接求(但是还要稍微优化一下)
题解如下
#include<iostream>
using namespace std;
long long find(long long n)
{
long long i; //注意⚠️这里的i一定要是 long long 否则 i * i 超过int 范围
int cnt = 0;
for(i = 1; i * i < n; i ++)
if(n % i == 0)
cnt += 2;
return cnt + (i * i == n);
}
int main()
{
long long n;
scanf("%lld", &n);
long long int tim = 0;
while(n != 2) n = find(n),tim ++;
printf("%lld", tim);
return 0;
}