|
课上看的题然后看错了，一直以为是要把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
d2?∣num， 即
n
u
m
=
d
×
k
num = d \times k
num=d×k
分类讨论
x
=
d
a
×
b
x = d^a \times b
x=da×b
-
)
a
=
1
a = 1
a=1, no -
)
a
=?
1
a \not = 1
a?=1 , b 是合数，yes -
)
a
=?
1
a \not = 1
a?=1 , b 是质数（包括1），d是质数，no -
)
a
=
2
a = 2
a=2 , b 是质数，no -
)
a
=?
2
a \not = 2
a?=2 , b 是质数，d是合数同时不是某个质数的幂次（可以把不同的质因数分开分配），yes -
)
a
=?
1
a \not = 1
a?=1 , b 是质数，d是合数同时是某个质数的幂次，
d
=
p
2
d = p ^ 2
d=p2且
x
=
p
7
x = p ^ 7
x=p7 则no，否则yes 浅证：设$d = p^k
,
如
果
, 如果
,如果a > 2 $ 且
k
>
1
k > 1
k>1， 可以将一个k拆成1和k-1两部分分给另外的数中的两个 ：
p
2
k
?
1
,
p
k
+
1
,
p
k
,
…
,
p
k
p ^{2k - 1}, p^{k + 1}, p^{k}, \dots, p^{k}
p2k?1,pk+1,pk,…,pk
d
=
p
2
d = p ^ 2
d=p2且
x
=
p
7
x = p ^ 7
x=p7 , 即 a= 3， k= 2， 因为幂次不能到4，（
d
2
?
∣?
?
n
u
m
d^2 \,\not| \,num
d2?∣num），找不出两种分配方式 另外总是能找出三个d作为基数，然后将剩下的再分配之后得到两种情况
#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[i?1][j]+dp[i][numi?j?]
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;
}
}
|