牛客多校第四场 B Basic Gcd Problem 题解

题目大意

定义函数$\large f_c(x) = max(1->x-1) c·f_c(gcd(i,x)) \quad x > 1$

$\large f_c(x) = 1 \quad x=1$。

求$\large f_c(n)$。

解题思路

很明显，答案肯定是$c^n$，所以我们需要使这个n尽可能的大。

由于质数与其他数的gcd都是1，所以我们不需要考虑质数。

那么对于其他的数来说，我们可以将他们分解成质因数相乘，每一个质因数就是相当于乘以一个c。

那么答案就只需要统计其质因数的数量然后用快速幂即可。

（我统计的时候乘就TLE了。。乘这么慢的吗。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5, mod = 1e9 + 7;
int num[N];

ll qpow(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b&1)    ans = ans*a%mod;
        a = a*a%mod,b>>=1;
    }
    return ans;
}

ll slove(int a) {
	ll ans = 0;
	for (int i = 2; i*i <= a; i++) {
		while (a % i == 0) {
			ans++;
			a /= i;
		}
	}
    if(a>1)    ans++;
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, c;
		cin >> n >> c;
		cout << qpow((ll)c,slove(n)) << endl;
	}
}