Codeforces Round #777 (Div. 2) D. Madoka and the Best School in Russia

课上看的题然后看错了,一直以为是要把x分成两个bea的数的乘积

prob. :

def 一个数good则 它是d的倍数, 一个数bea则 它good 同时 它不能表示成2个good的数的乘积,给一个good的数x ,问这个数能否表示成两个不同的bea的数的集合的乘积

ideas :

两种做法

一个数num如果是bea的,则$d ,| ,num $且 d 2 ∤ n u m d^2 \,\not| \,num d2num, 即 n u m = d × k num = d \times k num=d×k

分类讨论

x = d a × b x = d^a \times b x=da×b

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; const int M = 1010; ll primes[N], cnt = 0; bool st[N]; void sieve() { cnt = 0; for (ll i = 2; i < N; ++i) { if (!st[i]) primes[++cnt] = i; for (ll j = 1; primes[j] * i < N; ++j) { st[primes[j] * i] = 1; if (i % primes[j] == 0) break; } } } bool isPrime(int x) { for (int i = 1; primes[i] <= x / primes[i]; ++i) { if (x % primes[i] == 0) return false; } return true; } vector<pair<int, int> > factor(int x) { vector<pair<int, int> > res; for (int i = 1; primes[i] <= x / primes[i]; ++i) { if (x % primes[i] == 0) { int cnt = 0; while (x % primes[i] == 0) { x /= primes[i]; cnt++; } res.push_back({primes[i], cnt}); } } if (x > 1) res.push_back({x, 1}); return res; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); sieve(); int T; cin >> T; while (T--) { int x, d; cin >> x >> d; int a = 0; while (x % d == 0) { x /= d; a++; } if (a == 1) { cout << "NO" << endl; continue; } int b = x; if (!isPrime(b)) { cout << "YES" << endl; continue; } if (isPrime(d)) { cout << "NO" << endl; continue; } if(a == 2 && (isPrime(b) || b == 1)) { cout << "NO" << endl; continue; } vector<pair<int, int> > vec = factor(d); if (vec.size() > 1) { cout << "YES" << endl; continue; }  if (vec[0].second == 2 && a == 3 && vec[0].first == b) { cout << "NO" << endl; continue; } cout << "YES" << endl; } return 0; } 

DP

背包把方案算出来,把x表示成bea的数的乘积的方法有多少种

列出x的所有的因子

d p [ i ] [ j ] dp[i][j] dp[i][j] : 考虑了前i个数,当前的乘积是j的方案数,

转移 : d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j n u m i ] dp[i][j]= dp[i – 1][j] + dp[i][\frac{j}{num_i}] dp[i][j]=dp[i1][j]+dp[i][numij]

dp可以省掉一维,同时注意下标的处理,unordered_map 也会T

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 1e5 + 10; vector<ll> factor(ll x) { vector<ll> res; for (ll i = 1; i <= x / i; ++i) { if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } } sort(res.begin(), res.end()); return res; } ll dp[N], xid[N], yid[N];  ll x, d; ll getNum(ll num) { if(num < N) return xid[num]; return yid[x / num]; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); ll T; cin >> T; while (T--) { cin >> x >> d; auto vec = factor(x); for (ll i = 0; i <= 2000; ++i) { dp[i] = 0; } for (ll i = 0; i < vec.size(); ++i) {  if(vec[i]< N) xid[vec[i]] = i; else yid[x / vec[i]] = i; } dp[0] = 1; for (ll i = 0; i < vec.size(); ++i) { if (vec[i] % d == 0 && (vec[i] / d) % d != 0) { for (ll j = 0; j < vec.size(); ++j) { if(x /vec[i] % vec[j] != 0) continue; ll num = vec[i] * vec[j]; dp[getNum(num)] = min(2ll, dp[getNum(num)] + dp[j]); } } } if (dp[vec.size() - 1] >= 2) cout << "YES" << endl; else cout << "NO" << endl; } } 
本网页由快兔兔AI采集器生成,目的为演示采集效果,若侵权请及时联系删除。

原文链接:https://blog.csdn.net/qq_39602052/article/details/123484815

更多内容