题目描述

一天，小度坐在公园里学习时，灵机一动写下了这样一个运算式 $ f(x) = x^1 * (x - 1)^2 * (x - 2)^3 * ···· * 2^{(x-1)} * 1^x$ , 由于小度比较喜欢质数，他听说大数的质因子分解很难，现在小度想知道这个运算式取$n$时的质因子分解形式。

输入格式：

一行，一个整数 $n ( 1 \le x \le 10^7)$，表示运算式的输入。

输出格式：
一个字符串，表示$f(x)$的质因子分解形式，要求按照质因子从小到大排列，当指数为$1$时应当忽略指数，具体格式要求参见样例。

输入：

5

输出：

f(5)=2^8*3^3*5

题目分析

思路很明确，就是把多项式因式分解
目标多项式为
$ f(x) = x^1 * (x - 1)^2 * (x - 2)^3 * ···· * 2^{(x-1)} * 1^x$
要分解成
$ f(x) = 2^a * 3^b * 5^c * ····$的形式
那么我们只需要把原多项式中的非质数项分解成质因子相乘的形式

首先对于质因子的筛选，我们会想到欧拉筛

const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

那么仔细想一下不难发现，我们在欧拉筛中找到非质数的方法就是将质数相乘得到合数然后在标记成true
并且经过证明这个筛法不会落下任何一个合数
这样一来就简单了许多
可以知道我们每次找到的合数的两个因子是$primes[j]$和 $i$，
其中$primes[j]$是质数，$i$不一定是质数，那我们就把这两个数所对应的幂数加上该合数的幂数
但是这里筛的时候是从小开始筛，直接加上幂数的话会导致$i$还未分解成质因子时它的质因子就已经略过了
所以要先进行标记，记下每个合数的因子，然后再在后面从大到小累加幂数
剩下的就是输出了

记得开long long

C++代码

#include<bits/stdc++.h> 
#define int long long
using namespace std;

const int N = 10000010;
typedef pair<int , int> PII;

bool st[N] , is_prime[N];
int primes[N] , cnt; // 存质数
int ans[N];
PII divide[N];
int n;

void get_euler()
{
    for(int i = 2 ; i <= n ; i ++)
    {
        if(!st[i])
        {
            primes[cnt ++] = i;
            is_prime[i] = true;
        }
        for(int j = 0 ; primes[j] <= n / i ; j ++)
        {
            st[primes[j] * i] = true;
            divide[primes[j] * i] = {i , primes[j]}; // 先记下该合数的两个因子
            if(i % primes[j] == 0) break;
        }
    }

    for(int i = n ; i >= 2 ; i --)              // 从大到小遍历
    {
        if(is_prime[i]) continue;               // 如果本身就是质数的话不用再加一遍幂数
        auto t = divide[i];
        ans[t.first] += ans[i] , ans[t.second] += ans[i]; // 两个因子都要加上对应乘积合数的幂数
    }
}

signed main( )
{
    cin >> n;
    int idx = 0;
    for(int i = n ; i >= 2 ; i --) ans[i] = ++ idx;
    get_euler();

    cout << "f(" << n << ")=";
    for(int i = 0 ; i < cnt ; i ++)
    {
        if(i) cout << "*";
        if(ans[primes[i]] == 1) cout << primes[i] ;
        else cout << primes[i] << "^" << ans[primes[i]];
    }
    return 0;
}