#P1822. 第4题-小美的因子数量
-
1000ms
Tried: 127
Accepted: 13
Difficulty: 5
所属公司 :
美团
时间 :2024年4月13日
第4题-小美的因子数量
思路
二分 + 前缀和。
一个数的因子数等于其 每个质因子 pi 的数量加1 的乘积,即 i∏(cntpi+1)
q 次询问,要求我们单次查询需要控制在 O(logn) 内。
因为 10 以内只有 2,3,5,7 这 4 个质数,所以可以对这 4 个质数预处理前缀和
假设 l 在第 i 段,r 在第 j 段,那么 [l+1,j−1] 段的可以通过前缀和计算,
单独处理 i 段和 j 段,注意 i=j 的情况即可。
时间复杂度:O(nlogn)
代码
C++
// ac
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
int main()
{
cin.tie(0)->sync_with_stdio(false);
LL n, m, q;
cin >> n >> m;
const int mod = 1e9 + 7;
vector<int> primes = {2, 3, 5, 7};
vector<LL> s(m + 1);
vector<int> a(m + 1);
vector<array<LL, 4>> pre = vector<array<LL, 4>>(m + 1, {0});
auto get = [&](int x) -> vector<int> {
vector<int> cnt(4, 0);
for (int j = 0;j < 4;++ j) {
while(x % primes[j] == 0) {
x /= primes[j];
++ cnt[j];
}
}
return cnt;
};
for (int i = 1; i <= m; ++i)
{
cin >> a[i] >> s[i];
pre[i] = pre[i - 1];
vector<int> cnt = get(a[i]);
for (int j = 0;j < 4;++ j) {
pre[i][j] = (pre[i][j] + cnt[j] * s[i]) % mod;
}
s[i] += s[i - 1];
}
cin >> q;
while (q --) {
LL l, r;
cin >> l >> r;
int L = lower_bound(s.begin(), s.end(), l) - s.begin();
int R = lower_bound(s.begin(), s.end(), r) - s.begin();
vector<int> cnt(4, 0);
vector<int> cntl = get(a[L]), cntr = get(a[R]);
LL ans = 1;
for (int j = 0;j < 4;++ j) {
if (L == R) {
ans = ((r - l + 1) * cntl[j] % mod + 1) * ans % mod;
} else {
LL t = (s[L] - l + 1) % mod * cntl[j] % mod;
if (L < R) {
t += (r - s[R - 1]) % mod * cntr[j] % mod;
}
if (L + 1 < R) {
t += pre[R - 1][j] - pre[L][j];
}
t = (t % mod + mod) % mod;
ans = (t + 1) * ans % mod;
}
}
cout << ans << endl;
}
}
Python
# from bisect import bisect_left
n, m = map(int, input().split())
mod = 1000000007
table = {
1: [0, 0, 0, 0],
2: [1, 0, 0, 0],
3: [0, 1, 0, 0],
4: [2, 0, 0, 0],
5: [0, 0, 1, 0],
6: [1, 1, 0, 0],
7: [0, 0, 0, 1],
8: [3, 0, 0, 0],
9: [0, 2, 0, 0],
10: [1, 0, 1, 0]
}
index = [0 for i in range(1 + m)]
array = [0 for i in range(1 + m)]
pre = [[0 for i in range(4)] for j in range(1 + m)]
for i in range(1, m + 1):
u, v = map(int, input().split())
array[i] = u
u_list = table[u]
for j in range(4):
pre[i][j] = (pre[i - 1][j] + u_list[j] * v % mod) % mod
index[i] = index[i - 1] + v
# print(pre)
def check(index, m, x):
l = 1
r = m
while l <= r:
mid = (l + r) >> 1
if index[mid] == x:
return mid
elif index[mid] < x:
l = mid + 1
else:
r = mid - 1
return l
q = int(input())
for i in range(q):
l, r = map(int, input().split())
ll = check(index, m, l)
rl = check(index, m, r)
# print(ll, rl)
ans = 1
lu_list = table[array[ll]]
ru_list = table[array[rl]]
for j in range(4):
if ll == rl:
ans = ((r - l + 1) * lu_list[j] % mod + 1) * ans % mod
else:
tmp = (index[ll] - l + 1) % mod * lu_list[j] % mod
if ll < rl:
tmp += (r - index[rl - 1]) % mod * ru_list[j] % mod
if ll + 1 < rl:
tmp = (tmp + (pre[rl - 1][j] - pre[ll][j])) % mod
# tmp = (tmp % mod + mod) % mod
ans = (tmp + 1) * ans % mod
print(ans)
题目描述
小美拿到了一个数组,她有q次查询,每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗?
注:由于数组元素过多,所以是按连续段的方式给定。例如,[1,1,2,3,3,3]有2个1,1个2,3个3,因此表示为<2,1>,<1,2>,<3,3>。
输入描述
第一行输入两个正整数n,m,代表数组的大小,以及连续段的数量。 接下来的m行,每行输入两个正整数ui,vi,代表一段区间内有vi个ui
接下来的一行输入一个正整数q,代表询问次数。 接下来的q行,每行输入两个正整数l,r,代表询问的是第l个数到第r个数的乘积的因子数量
1≤n≤1014
1≤m,q≤105
1≤ui≤10
1≤vi≤109
1≤l,r≤n
保证所有的vi之和恰好等于n
输出描述
输出q行,每行输出一个整数,代表最终的乘积因子数量。由于答案可能过大,请对109+7取模
样例
输入
6 3
1 2
2 1
3 3
2
1 3
2 6
输出
2
8