房产汽车网站模板,湖北企业年报网上申报入口,网站安全防护措施,三只松鼠网络营销模式2024年4月13日美团春招实习试题【第四题:乘积因子数】-题目题解在线评测【二分】 题目描述#xff1a;输入描述输出描述样例 解题思路一#xff1a;python解题思路二#xff1a;c解题思路三#xff1a;0 题目描述#xff1a;
塔子哥拿到了一个数组#xff0c;她有q次查询… 2024年4月13日美团春招实习试题【第四题:乘积因子数】-题目题解在线评测【二分】 题目描述输入描述输出描述样例 解题思路一python解题思路二c解题思路三0 题目描述
塔子哥拿到了一个数组她有q次查询每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗?
注:由于数组元素过多所以是按连续段的方式给定。例如[1,1,2,3,3,3]有2个11个23个3因此表示为2,1,1,2, 3,3。
输入描述 第一行输入两个正整数n,m代表数组的大小以及连续段的数量。 接下来的m行每行输入两个正整数 u i , v i u_i,v_i ui,vi代表一段区间内有 v i v_i vi个 u i u_i ui 接下来的一行输入一个正整数q代表询问次数。 接下来的q行每行输入两个正整数l,r代表询问的是第l个数到第r个数的乘积的因子数量 1 ≤ n ≤ 1 0 14 1\le n\le 10^{14} 1≤n≤1014 1 ≤ m , q ≤ 1 0 5 1\le m,q\le 10^5 1≤m,q≤105 1 ≤ u _ i ≤ 10 1\le u\_i\le 10 1≤u_i≤10 1 ≤ v _ i ≤ 1 0 9 1\le v\_i\le 10^9 1≤v_i≤109 1 ≤ l , r ≤ n 1\le l,r\le n 1≤l,r≤n 保证所有的 v i v_i vi之和恰好等于n 输出描述 输出q行每行输出一个整数代表最终的乘积因子数量。由于答案可能过大请对1097取模 样例
输入
6 3
1 2
2 1
3 3
2
1 3
2 6输出
2
8OJ链接 https://codefun2000.com/p/P1822
乘积因子数量是指一个数的所有因子包括1和它本身的个数。要计算一个数的乘积因子数量可以按照以下步骤进行
将这个数分解成质因数的乘积。质因数是指不能再进行因数分解的素数比如2、3、5、7等。 对每个质因数的指数加1然后将它们相乘即可得到乘积因子数量。 举个例子我们来计算数值36的乘积因子数量
首先将36分解成质因数的乘积3622 ×3 2 对每个质因数的指数加1(21)×(21)3×39 所以36的乘积因子数量为9个。
解题思路一python # from bisect import bisect_left
n, m map(int, input().split())
mod 1000000007table {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] uu_list table[u]for j in range(4):pre[i][j] (pre[i - 1][j] u_list[j] * v % mod) % modindex[i] index[i - 1] vdef check(index, m, x):l 1r m 1while l r:mid (l r) 1# if index[mid] x:# return midif index[mid] x:l mid 1else:r midreturn lq 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 1lu_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 % modelse:tmp (index[ll] - l 1) % mod * lu_list[j] % modif ll rl:tmp (r - index[rl - 1]) % mod * ru_list[j] % modif ll 1 rl:tmp (tmp (pre[rl - 1][j] - pre[ll][j])) % mod# tmp (tmp % mod mod) % modans (tmp 1) * ans % modprint(ans)时间复杂度O(qlogn) 空间复杂度O(m)前缀和
解题思路二c
#include bits/stdc.husing namespace std;typedef long long LL;
#define endl \nint main()
{cin.tie(0)-sync_with_stdio(false);LL n, m, q;cin n m;const int mod 1e9 7;vectorint primes {2, 3, 5, 7};vectorLL s(m 1);vectorint a(m 1);vectorarrayLL, 4 pre vectorarrayLL, 4(m 1, {0});auto get [](int x) - vectorint {vectorint 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];vectorint 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();vectorint cnt(4, 0);vectorint 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;}
}时间复杂度O(qlogn) 空间复杂度O(m)前缀和
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
