质因数分解

代码模板

#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

例题 – 因子

令 X = n!, 给定一大于1的正整数p 求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子。
输入描述:
两个数n, p (1e18>= n>= 10000 >= p >= 2)
输出描述:
一个数
表示k
示例1
输入
10000 12
输出
4996

代码

思路

首先，我们知道对于任意一个数，我们都可以把他拆分成若干素因子乘积的形式如n=p^x+q^y+……r^z（p，q，……，r为素数），因为p<=n,所以p一定是n！的一个因子，所以p中含有的素因子n！中必定含有，并且幂次小于等于n！中该素因子的幂次。我们需要求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子，所以我们只要求p分解所得的每个素因子x的幂次ccount(x),对应于n！

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
ll n;
ll p;
int main()
{
    cin>>n>>p;
    ll k=1e18;
    for(int i=2;i<=p;i++)
    {
        if(p%i==0)
        {
            ll res=0,tmp=n;
            while(tmp)
            {
                res+=tmp/i;
                tmp/=i;
            }
            ll s=0;
            while(p%i==0)
            {
                p/=i;
                s++;
            }
            k=min(k,res/s);
        }
    }
    cout<<k<<endl;
    return 0;
}