2020牛客寒假算法基础集训营1 E题

这道题说实话并不难 主要是如何快速求出因子的个数
先把题目贴下来
链接 https://ac.nowcoder.com/acm/contest/3002/E

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

输入描述:
一个正整数 n(3<n<1e12)
请在这里输入引用内容

输出描述:
一个正整数，为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次。

但是我在这题卡了很久 超时很多次 说白了就是菜
先讲下做法 穷举加剪枝
先上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f(ll x){             //求x的因子个数
    ll i,res=0;
    for(i=1;i*i<x;i++){
        if(x%i==0)res+=2;
    }
    return res+(i*i==x);
}
int main(){
    ll i=0,n;
    cin>>n;
    while(n!=2)n=f(n),i++;
    cout<<i;
}

讲一下怎么剪枝 举个例子
16的因子有 1 2 4 8 16 看这个所有的因子都分在开根号的两边 而且个数相同
再看12 有 1 2 3 4 6 12 ，12开根号为2根号3 大于三小于4
这样可以有效的剪枝 在穷举的时候让i*i小于x就行 除了找到一个就乘二 然后若是开根号正好为一个整数就在加上这个数

还有一种做法 比较取巧 说实话我是完全不知道可以这样做的
先上代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

long long dcp(long long x){ 
    long long i,ans = 1;
    for(i = 2; i * i <= x; i++){
        if(x % i == 0){
            long long temp = 0;
            while(x % i == 0){
                x /= i;
                temp++;
            }
            ans *= (temp+1);
        }
    }
    if(x > 1) ans *= 2;
    return ans;
}
int main(){
    long long n,count=0;
    scanf("%lld",&n);
    while(n!=2){
        n=dcp(n);
        count++;
    }
    printf("%d\n",count);
    return 0; 
}

对着这个图片看下应该能看懂 来自zt大佬的手笔