「The 15th Zhejiang Provincial」F.Now Loading!!!(数论+二分)

描述

传送门:我是传送门

DreamGrid has $n$ integers $a_1,a_2,\dots,a_n$. DreamGrid also has $m$ queries, and each time he would like to know the value of

for a given number $p$, where $\lfloor x \rfloor = \max{y \in \mathbb{Z} \mid y \le x}$, $\lceil x \rceil = \min{y \in \mathbb{Z} \mid y \ge x}$.

输入

There are multiple test cases. The first line of input is an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \times 10^5$) — the number of integers and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10^{9}$).

The third line contains $m$ integers $p_1, p_2, \dots, p_m$ ($2 \le p_i \le 10^{9}$).

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $2 \times 10^6$.

输出

For each test case, output an integer $(\sum\limits_{i=1}^{m} i \cdot z_i) \bmod 10^9$, where $z_i$ is the answer for the $i$-th query.

样例

输入

2
3 2
100 1000 10000
100 10
4 5
2323 223 12312 3
1232 324 2 3 5

输出

11366
45619

思路

这道题的所有题解我全都看了一遍,基本思路大致搞明白,但是卡在最后的一句代码上

1
ans = (ans+tmp*j)%mod;

最后我发现($*j$)是题目要求的,是时候换个眼睛脑子了😤

刚开始毫无头绪(现在看完别人的题解也是没有头绪···

现场赛之前再回头看一下这个题目吧,这次不写题解了,我现在也实在写不出了来几句···

另外,为什么ZOJ爆内存提示段错误????

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*
* =================================================================
*
* Filename: zoj4029.cpp
*
* Link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4029
*
* Version: 1.0
* Created: 2018/10/22 21时11分39秒
* Revision: none
* Compiler: g++
*
* Author: 杜宁元 (https://duny31030.top/), duny31030@126.com
* Organization: QLU_浪在ACM
*
* =================================================================
*/
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=n;i>=a;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9;
const int N = 5e5+100;
ll a[N];
ll t,n,m,x;
ll sum[N][32];

// 1.对于每一次询问p,枚举分母 i 时,可以找出a中分母等于 i 的那一段
// 预处理前缀和,用于此时直接加。

int main()
{
ios
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
scanf("%lld",&t);
while(t--)
{
scanf("%lld %lld",&n,&m);
rep(i,1,n) scanf("%lld",&a[i]);
// rep(i,1,m) scanf("%d",&p[i]);
sort(a+1,a+1+n);
// rep(i,1,n) printf("%lld ",a[i]); printf("\n");
// 打表预处理
for(ll k = 1;k <= 30;k++)
for(ll i = 1;i <= n;i++)
sum[i][k] = sum[i-1][k]+a[i]/k;

ll ans = 0;
for(ll j = 1;j <= m;j++)
{
scanf("%lld",&x);
ll pos;
ll up = x;
ll k = 1;
ll tmp = 0;
for(ll i = 1;i <= n;i = pos+1)
{
// printf("up = %lld\n",up);
pos = i-1;
ll l = i,r = n;
while(l <= r)
{
ll mid = (l+r)>>1;
if(a[mid] <= up)
{
pos = mid;
l = mid+1;
}
else
r = mid-1;
}
tmp = (tmp+sum[pos][k]-sum[i-1][k]+mod)%mod;
k++;
up *= x;
}
//// printf("tmp = %lld j = %lld tmp*j = %lld ans = %lld\n",tmp,j,tmp*j,ans+tmp*j);
ans = (ans+tmp*j)%mod;
}
printf("%lld\n",ans);
}

fclose(stdin);
// fclose(stdout);
return 0;
}