B3871 [GESP202309 五级] 因数分解 题解

· · 题解

B3871 [GESP202309 五级] 因数分解 题解

这道题乍一看不难，其实也不难

这道题使用了因式分解。

直接上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,f=0;//f代表本因数是否是最小的质因数，如果是，不用在前面加 * 
    cin>>n;
    for(ll i=2;i*i<=n;i++)//枚举数
    {
        if(n%i==0)//因数
        {
            if(f) cout<<" * ";//见上
            cout<<i;//输出该质因数
            f=1;
            ll z=0;//指数个数
            while(n%i==0)
            {
                n/=i;//每次都将所有一样的质因数除尽，保证下一次枚举到的因数都是质数
                z++;//指数增加
            }
            if(z>1) cout<<'^'<<z;//如果指数为1则不需次方
        }
    }
    if(n>1)//如果n大于1，说明并没有完全除尽，但这个数一定是质数，且指数为1
    {
        if(f) cout<<" * ";
        cout<<n;
    }
    return 0;
}

AC 记录~