# weekly-contest-326

## A

### Statement

``````输入：num = 7

``````

``````输入：num = 121

``````

``````输入：num = 1248

``````

• `1 <= num <= 109`
• `num` 的数位中不含 `0`

Given an integer `num`, return the number of digits in `num` that divide `num`.

An integer `val` divides `nums` if `nums % val == 0`.

Example 1:

``````Input: num = 7
Output: 1
Explanation: 7 divides itself, hence the answer is 1.
``````

Example 2:

``````Input: num = 121
Output: 2
Explanation: 121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2.
``````

Example 3:

``````Input: num = 1248
Output: 4
Explanation: 1248 is divisible by all of its digits, hence the answer is 4.
``````

Constraints:

• `1 <= num <= 109`
• `num` does not contain `0` as one of its digits.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int countDigits(int num) {
auto v = vector<int>();
int x = num;

while (x) {
v.push_back(x % 10);
x /= 10;
}

int res = 0;

for (const auto &a : v) {
if (num % a == 0) {
++res;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 质数 是指大于 `1` 且仅能被 `1` 及自身整除的数字。
• 如果 `val2 / val1` 是一个整数，则整数 `val1` 是另一个整数 `val2` 的一个因数。

``````输入：nums = [2,4,3,7,10,6]

nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7 。

``````

``````输入：nums = [2,4,8,16]

nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 210 。

• `1 <= nums.length <= 104`
• `2 <= nums[i] <= 1000`

Given an array of positive integers `nums`, return the number of distinct prime factors in the product of the elements of `nums`.

Note that:

• A number greater than `1` is called prime if it is divisible by only `1` and itself.
• An integer `val1` is a factor of another integer `val2` if `val2 / val1` is an integer.

Example 1:

``````Input: nums = [2,4,3,7,10,6]
Output: 4
Explanation:
The product of all the elements in nums is: 2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7.
There are 4 distinct prime factors so we return 4.
``````

Example 2:

``````Input: nums = [2,4,8,16]
Output: 1
Explanation:
The product of all the elements in nums is: 2 * 4 * 8 * 16 = 1024 = 210.
There is 1 distinct prime factor so we return 1.
``````

Constraints:

• `1 <= nums.length <= 104`
• `2 <= nums[i] <= 1000`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

const int N = 1e3 + 10;
int pri[N], check[N];
void sieve() {
memset(check, 0, sizeof check);
*pri = 0;
for (int i = 2; i < N; ++i) {
if (!check[i]) {
pri[++*pri] = i;
}
for (int j = 1; j <= *pri; ++j) {
if (1ll * i * pri[j] >= N)
break;
check[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
}
}

class Solution {
public:
int distinctPrimeFactors(vector<int> &nums) {
sieve();

set<int> se;

sort(all(nums));
nums.erase(unique(all(nums)), nums.end());

for (const auto &a : nums) {
if (check[a] == 0) {
se.insert(a);
} else {
for (int i = 2; i <= a; i++) {
if (check[i] == 0 && a % i == 0) {
se.insert(i);
}
}
}
}

return int(se.size());
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• `s` 中每个数位 恰好 属于一个子字符串。
• 每个子字符串的值都小于等于 `k` 。

• 一个字符串的  是这个字符串对应的整数。比方说，`"123"` 的值为 `123` ，`"1"` 的值是 `1` 。
• 子字符串 是字符串中一段连续的字符序列。

``````输入：s = "165462", k = 60

``````

``````输入：s = "238182", k = 5

``````

• `1 <= s.length <= 105`
• `s[i]` 是 `'1'` 到 `'9'` 之间的数字。
• `1 <= k <= 109`

You are given a string `s` consisting of digits from `1` to `9` and an integer `k`.

A partition of a string `s` is called good if:

• Each digit of `s` is part of exactly one substring.
• The value of each substring is less than or equal to `k`.

Return the minimum number of substrings in a good partition of `s`. If no good partition of `s` exists, return `-1`.

Note that:

• The value of a string is its result when interpreted as an integer. For example, the value of `"123"` is `123` and the value of `"1"` is `1`.
• A substring is a contiguous sequence of characters within a string.

Example 1:

``````Input: s = "165462", k = 60
Output: 4
Explanation: We can partition the string into substrings "16", "54", "6", and "2". Each substring has a value less than or equal to k = 60.
It can be shown that we cannot partition the string into less than 4 substrings.
``````

Example 2:

``````Input: s = "238182", k = 5
Output: -1
Explanation: There is no good partition for this string.
``````

Constraints:

• `1 <= s.length <= 105`
• `s[i]` is a digit from `'1'` to `'9'`.
• `1 <= k <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minimumPartition(string s, int k) {
int n = int(s.size());
auto f = vector<int>(n + 5, INF);
f[0] = 0;

for (int i = 1; i <= n; i++) {
ll cur = 0;
ll base = 1;

for (int j = i; j >= 1; j--) {
cur += base * (s[j - 1] - '0');
base *= 10;

if (cur > k) {
break;
}

// cout << i << " " << j << " " << cur << endl;

if (f[j - 1] != INF) {
f[i] = min(f[i], f[j - 1] + 1);
}
}
}

if (f[n] == INF) {
return -1;
}

return f[n];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• `left <= nums1 < nums2 <= right ` 。
• `nums1` 和 `nums2` 都是 质数 。
• `nums2 - nums1` 是满足上述条件的质数对中的 最小值 。

``````输入：left = 10, right = 19

``````

``````输入：left = 4, right = 6

``````

• `1 <= left <= right <= 106`

Given two positive integers `left` and `right`, find the two integers `num1` and `num2` such that:

• `left <= nums1 < nums2 <= right `.
• `nums1` and `nums2` are both prime numbers.
• `nums2 - nums1` is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array `ans = [nums1, nums2]`. If there are multiple pairs satisfying these conditions, return the one with the minimum `nums1` value or `[-1, -1]` if such numbers do not exist.

A number greater than `1` is called prime if it is only divisible by `1` and itself.

Example 1:

``````Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.
``````

Example 2:

``````Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.
``````

Constraints:

• `1 <= left <= right <= 106`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

const int N = 1e6 + 10;
int pri[N], check[N];
void sieve() {
memset(check, 0, sizeof check);
*pri = 0;
for (int i = 2; i < N; ++i) {
if (!check[i]) {
pri[++*pri] = i;
}
for (int j = 1; j <= *pri; ++j) {
if (1ll * i * pri[j] >= N)
break;
check[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
}
}

class Solution {
public:
vector<int> closestPrimes(int left, int right) {
if (*pri == 0) {
sieve();
}

if (left == 1) {
++left;
}

auto f = vector<int>();
for (int i = left; i <= right; ++i) {
if (check[i] == 0) {
f.push_back(i);
}
}

int n = int(f.size());

int diff = 0x3f3f3f3f;
int res = -1;

for (int i = 1; i < n; i++) {
if (f[i] - f[i - 1] < diff) {
diff = f[i] - f[i - 1];
res = i;
}
}

if (res == -1) {
return {
-1,
-1,
};
}

return {
f[res - 1],
f[res],
};
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````