rin和快速迭代

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

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

输出描述:

一个正整数，为 

迭代至

的次数。
示例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 
 2 #include <set>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include <string>
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
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;i35 #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 }
数论

相关

「笔记」数论知识整理

【数论】【差分】Row GCD

快速数论变换（NTT）

ABC222 G - 222（数论）

数论的一些简单定理证明

数论基础（素数筛选）

[CF615D] Multipliers - 数论

[CF1493D] GCD of an Array - 数论,map,set

【题解】BZOJ-4176 Lucas的数论

简单数论：最大公因数与最小公倍数问题

【初等数论】乘法逆元略解

数论-孙子定理（中国剩余定理）及应用

标签