Given an integer array arr[n] and an integer d, count the number of distinct triplets (i, j, k) where 0 <= i < j < k < n and arr[i] + arr[j] + arr[k] is divisible by d.
Example: arr = [2, 3, 1, 6], d = 3 → 2 (triplets (0,1,2) and (0,2,3)).
Constraints
3 ≤ n ≤ 10³, 1 ≤ arr[i] ≤ 10⁹, 2 ≤ d ≤ 10⁶.
解法
统计模 d 各余数的频次，再求满足 r1 + r2 + r3 ≡ 0 (mod d) 的有序三元组数。重复余数用二项系数处理。复杂度 O(n + d²)。
from math import comb
def get_triplet_count(a, d):
cnt = [0] * d
for x in a:
cnt[x % d] += 1
ans = 0
for r1 in range(d):
for r2 in range(r1, d):
r3 = (d - (r1 + r2) % d) % d
if r3 < r2:
continue
if r1 == r2 == r3:
ans += comb(cnt[r1], 3)
elif r1 == r2:
ans += comb(cnt[r1], 2) * cnt[r3]
elif r2 == r3:
ans += cnt[r1] * comb(cnt[r2], 2)
else:
ans += cnt[r1] * cnt[r2] * cnt[r3]
return ansclass Solution {
static long getTripletCount(int[] a, int d) {
long[] cnt = new long[d];
for (int x : a) cnt[((x % d) + d) % d]++;
long ans = 0;
for (int r1 = 0; r1 < d; r1++)
for (int r2 = r1; r2 < d; r2++) {
int r3 = ((d - (r1 + r2) % d) % d);
if (r3 < r2) continue;
if (r1 == r2 && r2 == r3) ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) / 6;
else if (r1 == r2) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r3];
else if (r2 == r3) ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) / 2;
else ans += cnt[r1] * cnt[r2] * cnt[r3];
}
return ans;
}
}#include <vector>
using namespace std;
long long getTripletCount(vector<int>& a, int d) {
vector<long long> cnt(d, 0);
for (int x : a) cnt[((x % d) + d) % d]++;
long long ans = 0;
for (int r1 = 0; r1 < d; r1++)
for (int r2 = r1; r2 < d; r2++) {
int r3 = ((d - (r1 + r2) % d) % d);
if (r3 < r2) continue;
if (r1 == r2 && r2 == r3) ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) / 6;
else if (r1 == r2) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r3];
else if (r2 == r3) ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) / 2;
else ans += cnt[r1] * cnt[r2] * cnt[r3];
}
return ans;
}Two integers are considered coprime if their greatest common divisor (GCD) is 1.
Given an array A of positive integers, return an array B of length len(A) where B[i] represents the count of integers in [1, A[i]] (inclusive) that are co-prime with A[i].
Example: A = [5, 8, 14] → B = [4, 4, 6].
Constraints
1 ≤ A[i] ≤ 10⁵.
解法
B[i] 即欧拉函数 φ(A[i])。对每个值用 sqrt(A[i]) 内的试除分解质因数，再套 φ(n) = n · Π(1 − 1/p)。复杂度 O(n · sqrt(max A))。
def coprime_count(A):
def phi(n):
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
return [phi(x) for x in A]class Solution {
static int phi(int n) {
int res = n;
for (int p = 2; (long) p * p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
static int[] coprimeCount(int[] A) {
int[] out = new int[A.length];
for (int i = 0; i < A.length; i++) out[i] = phi(A[i]);
return out;
}
}#include <vector>
using namespace std;
int phi(int n) {
int res = n;
for (int p = 2; (long long) p * p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
vector<int> coprimeCount(vector<int>& A) {
vector<int> out;
out.reserve(A.size());
for (int x : A) out.push_back(phi(x));
return out;
}A trading firm predicts stock prices of a commodity for the next n days. A period of consecutive days is investable if the maximum price in the period is max_price and the minimum price is min_price. Given price[n], count the number of subarrays whose max equals max_price and min equals min_price.
Example: price = [1, 2, 3, 2], max_price = 3, min_price = 2 → 3 (subarrays [2,3], [2,3,2], [3,2]).
解法
枚举左端点 l，右端点 r 向右延伸，维护当前最大/最小值；越界提前停止，两端都满足则计数。复杂度 O(n²)。
def count_investable_periods(price, mx, mn):
n = len(price)
cnt = 0
for l in range(n):
cur_max = cur_min = price[l]
for r in range(l, n):
cur_max = max(cur_max, price[r])
cur_min = min(cur_min, price[r])
if cur_max > mx or cur_min < mn:
break
if cur_max == mx and cur_min == mn:
cnt += 1
return cntclass Solution {
static long countInvestablePeriods(int[] price, int mx, int mn) {
int n = price.length;
long cnt = 0;
for (int l = 0; l < n; l++) {
int curMax = price[l], curMin = price[l];
for (int r = l; r < n; r++) {
curMax = Math.max(curMax, price[r]);
curMin = Math.min(curMin, price[r]);
if (curMax > mx || curMin < mn) break;
if (curMax == mx && curMin == mn) cnt++;
}
}
return cnt;
}
}#include <vector>
#include <algorithm>
using namespace std;
long long countInvestablePeriods(vector<int>& price, int mx, int mn) {
int n = price.size();
long long cnt = 0;
for (int l = 0; l < n; l++) {
int curMax = price[l], curMin = price[l];
for (int r = l; r < n; r++) {
curMax = max(curMax, price[r]);
curMin = min(curMin, price[r]);
if (curMax > mx || curMin < mn) break;
if (curMax == mx && curMin == mn) cnt++;
}
}
return cnt;
}