给定你一个正整数nn。并给定你一个函数F(n)F(n),该函数的值为nn的所有因子(不包括他本身)加起来的和。 现在你在研究一个问题要把nn变为1,需要迭代多少次FF函数。 当n=12n=12时他的迭代过程为
12 -> 1 + 2 + 3 + 4 + 6 = 16
16 -> 1 + 2 + 4 + 8 = 15
15 -> 1 + 3 + 5 = 9
9-> 1 + 3 = 4
4-> 1 + 2 = 3
3-> 1 = 1
所有他的迭代次数是6次 请你输出当n=720n=720的迭代次数 (代码需要5-10秒运行,不知道有没有更方便的)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n,sum;
ll solve(ll n)
{
ll x=1;
for(ll i=2;i*i<=n;i++){
if(n%i!=0) continue;
if(i*i==n){
x+=i;break;
}else{
x=x+i+n/i;
}
}
return x;
}
int main()
{
ll n=720,sum=0;
while(n>1){
sum++;
n=solve(n);
cout<<n<<endl;
}
cout<<sum<<endl;//194
}