rin和快速迭代

链接：https://ac.nowcoder.com/acm/contest/3002/E

rin最近喜欢上了数论。
然而数论实在太复杂了，她只能研究一些简单的问题。
这天，她在研究正整数因子个数的时候，想到了一个“快速迭代”算法。设 $f(x)\$ 为 $x\$ 的因子个数，将 $f\$ 迭代下去，rin猜想任意正整数最终都会变成 $2\$ 。
例如： $f(12)=6，f(6)=4，f(4)=3，f(3)=2 \$ 。
她希望你帮她验证一下。她会给你一个正整数 $n\$ ，让你输出它在迭代过程中，第一次迭代成 $2\$ 的迭代次数。

输入描述:

一个正整数

$n\$ $(3≤n≤10^{12})\$

输出描述:

一个正整数，为

$n\$

迭代至

$2\$

的次数。

示例1

输入 12

输出 4

说明

12的因子：1，2，3，4，6，12。共6个。

6的因子：1，2，3，6。共4个。

4的因子：1，2，4。共3个。

3的因子：1，3。共2个。

12 → 6 → 4 → 3 → 2 ，故迭代了4次。

思路：一道简单的数论题（勉强算？？？），的根据题目的数据范围以及时间，直接用一个 O(√n) 的时间复杂度的求因子个数的函数就行。

代码：

 1 #include <map>

 2 #include <set>

 3 #include <list>

 4 #include <stack>

 5 #include <queue>

 6 #include <deque>

 7 #include <cmath>

 8 #include <ctime>

 9 #include <string>

10 #include <limits>

11 #include <cstdio>

12 #include <vector>

13 #include <iomanip>

14 #include <cstdlib>

15 #include <cstring>

16 #include <istream>

17 #include <iostream>

18 #include <algorithm>

19 #define ci cin

20 #define co cout

21 #define el endl

22 #define Scc(c) scanf("%c",&c)

23 #define Scs(s) scanf("%s",s)

24 #define Sci(x) scanf("%d",&x)

25 #define Sci2(x, y) scanf("%d%d",&x,&y)

26 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z)

27 #define Scl(x) scanf("%I64d",&x)

28 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y)

29 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z)

30 #define Pri(x) printf("%d\n",x)

31 #define Prl(x) printf("%I64d\n",x)

32 #define Prc(c) printf("%c\n",c)

33 #define Prs(s) printf("%s\n",s)

34 #define For(i,x,y) for(int i=x;i<y;i++)

35 #define For_(i,x,y) for(int i=x;i<=y;i++)

36 #define FFor(i,x,y) for(int i=x;i>y;i--)

37 #define FFor_(i,x,y) for(int i=x;i>=y;i--)

38 #define Mem(f, x) memset(f,x,sizeof(f))

39 #define LL long long

40 #define ULL unsigned long long

41 #define MAXSIZE 100005

42 #define INF 0x3f3f3f3f

43

44 const int mod=2e7;

45 const double PI = acos(-1.0);

46

47 using namespace std;

48

49 int count(LL n)

50 {

51     int s=1;

52     for(int i=2; i*i<=n; i++)

53     {

54         if(n%i==0)

55         {

56             int a=0;

57             while(n%i==0)

58             {

59                 n/=i;

60                 a++;

61             }

62             s=s*(a+1);

63         }

64     }

65     if(n>1) s=s*2;

66     //当n大于1时，说明还有一个因子的幂时1，故乘上（1+1）即为最终答案。

67     return s;

68 }

69 int main()

70 {

71     LL n;

72     ci>>n;

73     int cnt=1;

74     while(1)

75     {

76         int tmp=count(n);

77         if(tmp==2)

78             break;

79         cnt++;

80         n=tmp;

81

82     }

83     Pri(cnt);

84     return 0;

85 }

巴特西

rin和快速迭代

输出描述:

输入 12

输出 4

说明

最新文章

热门文章