牛客周赛143#题解#C题/小红的因子幂和

传送门->小红的因子幂和

题目要求如图所示

本题考察知识点

1.约数（因子）构造理论

介绍：若 \(v = x \times y\)，则 \(v\) 的任意因子 \(d\) 都可以拆解为 \(d = d_1 \times d_2\)（其中 \(d_1 | x, d_2 | y\)）。翻译：如果 \(d\) 是 \(x \times y\) 的约数，那么 \(d\) 一定可以表示为 \(d = d_1 \times d_2\)，其中 \(d_1\) 是 \(x\) 的某个约数，\(d_2\) 是 \(y\) 的某个约数。

证明

2.质因子分解

3.快速幂

4.模运算性质

---

大致思路：

分别算出两个数的所有因数，乘起来去重，再用快速幂硬算

\(ACcode:\)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define int long long
#define i128 __int128aconst int mod = 1e9 + 7;
const int MOD = 998244353;const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};ll ksm(ll a, ll b, ll p) {ll ans = 1;a %= p;while(b) {if(b & 1) ans = (ans * a) % p;b >>= 1;a = (a * a) % p;}return ans % p;
}std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {std::uniform_int_distribution<int> distribution(l, r);return distribution(rng);
}void solve() {int x, y;cin >> x >> y;set<int>st1,st2 ;for(int i = 1;i * i <= x;i++){if(x % i == 0){st1.insert(i) ;if(i * i != x){st1.insert(x/i) ;}}}for(int i = 1;i * i <= y;i++){if(y % i == 0){st2.insert(i) ;if(i * i != y){st2.insert(y/i) ;}}}set<int>st3 ;for(auto & a1 : st1){for(auto & a2 : st2){st3.insert(a1 * a2) ;}}int sum = 0 ;for(auto & k : st3){sum = (sum + ksm(k,k,mod) ) % mod ;}cout << sum << "\n" ;
}
signed main () {// init(minp, primes, m); // primesios::sync_with_stdio(0);cin.tie(0), cout.tie(0);// init();solve();return 0;
}```