题解 CF935A 【Fafa and his Company】

· · 题解

数论题不是用来氵的

所以，我们果断地选择了分解质因数

于是就可以用公式：

n=(p_{1}^{a_{1}})*(p_{2}^{a_{2}})*...*(p_{k}^{a_{k}})

n的因子个数 =(a_{1}+1)*(a_{2}+1)*...*(a_{k}+1)

代码：

#include <cstdio>
int n,ans=1;
int main(void){
    scanf ("%d",&n);
    for (int i=2;i<=n;i++)if (n%i==0){
        int k=0;
        while (n%i==0)n/=i,k++;//分解质因数，看有多少重
        ans*=(k+1);
    }
    printf ("%d",ans-1);
}