GYM 100090 D.Insomnia（递归）

Description
给出一整数n，每次可以除一个n的不是1的因子，一直到除到n变成1为止，问有多少种方案
Input
一个整数n(1<=n<=1e6)
Output
输出n可以通过多少种方案变成1
Sample Input
10
Sample Output
3
Solution
枚举n的因子，然后递归去求n除去该因子后变成1的方案数累加到n的答案上，记忆化一下即可
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 1111111
int ans[maxn];
int Solve(int n)
{
    if(ans[n]!=-1)return ans[n];
    int temp=0;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
        {
            temp+=Solve(i);
            if(i*i!=n)temp+=Solve(n/i);
        }
    return ans[n]=temp+1;
}
int main()
{
    int n;
    while(~scanf("%d",&n))printf("%d\n",Solve(n));
    return 0;
}