【培训题】唯一分解定理应用[1]P1945

Description

质因子分解是数论中一个基本定理，见P1128。现在请你利用这个基本定理，对给定整数n，完成下列三个任务： 任务1、计算n的因数个数并由小到大输出这些因数； 任务2、计算n的因数和； 任务3、计算1,2,…,n中与n互素的数个数：phi(n)；

Input

若干组数据，每组数据一行，表示整数n。

Output

第一行是任务1的结果，第一个整数表示整数n的因数个数，接下来若干整数表示n的因数（由小到达输出）。第二行是任务2的结果。第二行，一个整数，表示phi(n)。

Hint

反正要用long long。

Solution

这道题只能用公式来算phi，不能用欧拉筛因为数组不可能开到long long的位数那么大，然后的话为什么可以用公式是因为n一定是它的质因子的倍数所以一定能整除，然后需要注意的是输入输出的lld（你已经死在这上面至少十次了少女）。

#include
#include
#include
#include
#include
#include
#define int long long
#define maxn 10000005
using namespace std;
int ans[maxn];
int cnt,ans1=1,ans2,cntt,n,ans3;
inline int phii(int x){
    ans3=n;
    for(int i=2;i<=sqrt(n+1);i++){
        if(x%i==0){
            ans3=ans3*(i-1)/i;
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1){
        ans3=ans3*(x-1)/x;
    }
}
inline void Factor(int x){
    for(int i=1;i<=sqrt(x+1);i++){
        if(x%i==0){
            ans[++cntt]=i;
            if(i!=x/i)ans[++cntt]=x/i;
        }
    }
    sort(ans+1,ans+cntt+1);
    for(int i=1;i<=cntt;i++){
        printf(" %lld",ans[i]);
        ans2+=ans[i];
    }
    printf("\n");
}
inline void workk(int x){
    vectora;
    vectorb;
    int k=0;
    for(int i=2;i<=sqrt(x+1);i++){
        if(x%i==0){
            k=0;
            a.push_back(i);
            while(x%i==0){
                x/=i;
                k++;
            }
            b.push_back(k);
        }
    }
    if(x>1){
        a.push_back(x);
        b.push_back(1);
    }
    for(int i=0;i