EducationalCodeForcesRound48

Educational Codeforces Round 48 (Rated for Div. 2)

A.Death Note

题目大意:告诉你你一天可以写\(a_i\)个字, 现在你有一本\(DeathNote\),这本书有\(n\)页,每页可以写\(m\)个字,问每天如果写\(a_i\)个字的话,一天要翻多少页

题解:你搞一个 \(sum\) 记录当前页你已经写了多少个字,然后每天要翻的页数就是$ $, \(sum = (sum + a_i)\%m\)

代码:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 5;

int a[maxn], n, m, ans;

LL sum;

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}
int main(){
n = read(); m = read();
for(register int i = 1; i <= n; i++)a[i] = read();
for(register int i = 1; i <= n; i++){
sum += a[i]; ans = sum / m;
//while(sum >= m)ans++, sum -= m;
sum %= m;
printf("%d ", ans);
}
return 0;
}

B.Segment Occurrences

题目大意:给你一个串\(s_0\) , 再给你一个匹配串\(s_1\) ,有\(m\)次询问每次问你\(s_0\)这个串在\([l, r]\)这个区间内,出现了多少次\(s_1\)

题解:由于\(len(s_1) \leq 10^3\) , \(len(s_0) \leq 10^5\) ,所以我们直接对于\(s_0\)中的每一位的后\(len(s_1)\)位和\(s_1\)匹配一下,然后\(a_i = (s_1==s_{0l, r})\) ,用这个数组搞一下前缀和,每次之久\(O(1)\)查询就好了,但是注意如果查询\([l,r]\)区间最后的答案是\(sum[r - len(s_1) + 1] - sum[l - 1]\)而不是\(sum[r]-sum[l-1]\),然后匹配我用的是哈希,当然\(KMP\), 暴力匹配都是可以的

代码:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ull;

const int maxn = 2e3 + 5;
const int seed0 = 233;
const int seed1 = 23331;

int Q, sum[maxn], n, m;
char s[maxn], s1[maxn];
struct Hash{
ull base0, base1;
Hash(ull X = 0, ull X0 = 0){base0 = X; base1 = X0;}
bool operator == (const Hash &t) const {return base0 == t.base0 && base1 == t.base1;}
}ex, op[maxn];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline Hash gethash(int pos, int len, char *s){
ull base0 = 0, base1 = 0;
for(register int i = pos; i <= pos + len - 1; i++)
base0 = base0 * seed0 + s[i];
for(register int i = pos; i <= pos + len - 1; i++)
base1 = base1 * seed1 + s[i];
return Hash(base0, base1);
}

int main(){
n = read(); m = read(); Q = read();
scanf("%s%s", s + 1, s1 + 1);
ex = gethash(1, m, s1);
for(register int i = 1; i + m - 1 <= n; i++){
op[i] = gethash(i, m, s);
sum[i] = sum[i - 1] + (op[i] == ex);
}
for(register int i = 1; i <= Q; i++){
int l = read(), r = read();
if(r - l + 1 < m)printf("0\n");
else printf("%d\n", sum[r - m + 1] - sum[l - 1]);
}
return 0;
}

C.Vasya And The Mushrooms

题目大意:有两排蘑菇,每行有\(n\)个,每个蘑菇都有一个生长速度\(a_i\), 一开始的初始时间是零,你在两个个子之间移动的速度是\(1m/s\) 每个相邻的格子之间的距离是一,最后你得到每个蘑菇的权值是\(a_i\cdot t_i\)\(t_i\)是你猜到这个蘑菇的时间,问你如何采摘才能让总权值最大

题解:这题然我们一次性拿完并且不能经过相同的蘑菇,那么很显然如果你在某一行上走的路径长度超过二的话那么你就必须得走到头然后从另一行绕回来,那么我们就可以枚举一下是从那一行的哪一列开始一直向前走的,此前我们必须得走蛇形的,例如:

所以我们枚举一下转折点就好了,关于统计答案我们处理一个蛇行走的第一行和第二行的前缀和(就是在蛇行走时的前缀和)分别为 \(s_0, s_1\),和一个前缀和分别为\(ss_0, ss_1\),和一个后缀和\(sss_0, sss_1\),还有一个这样的东西 \[ ssa_{i} = \sum_{j=1}^{j\leq i}i\cdot a_j \] 和这样一个东西 \[ ssb_{1i}=\sum_{j=i}^{j \leq n}(n - j + 1) \cdot a_j \] 所以说对于一个转折点在第一行第\(i\)列的情况来说 \[ ans = s_{0i} + s_{1i} + (sum_{0n} - sum_{0i} + i \cdot (ss_{0n} - ss_{0i})) + (ssb_{1i} - ssb_{1n} + (n + i) \cdot (sss_{1i} - sss_{1n})) \] 还有一个是就是转折点在第二行第\(i\)列的情况,我就不打了,写着好麻烦,见代码,其实就是懒

代码:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ull;

const int maxn = 3e5 + 5;
const int seed0 = 233;
const int seed1 = 23331;

int n, a[maxn], b[maxn];

LL ans, sum, sa[maxn], sb[maxn], ssa0[maxn], ssb0[maxn], ssa1[maxn], ssb1[maxn], s0[maxn], s1[maxn];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main(){
n = read();
for(register int i = 1; i <= n; i++)
s0[i] = s0[i - 1] + (a[i] = read());
for(register int i = 1; i <= n; i++)
s1[i] = s1[i - 1] + (b[i] = read());
for(register int i = 1; i <= n; i++)
ssb0[i] = ssb0[i - 1] + 1ll * i * b[i];
for(register int i = n; i >= 1; i--)
ssa1[i] = ssa1[i + 1] + 1ll * (n - i + 1) * a[i];
for(register int i = 1; i <= n; i++)
ssa0[i] = ssa0[i - 1] + 1ll * i * a[i];
for(register int i = n; i >= 1; i--)
ssb1[i] = ssb1[i + 1] + 1ll * (n - i + 1) * b[i];
ans = max(ans, sum);
// -------------------------------------------------- // task 3
sum = 0;
for(register int i = 1, tim = 1; i <= n; i += 2, tim += 4){
if(i <= n)sb[i] = sb[i - 1] + 1ll * tim * b[i];
if(i < n)sb[i + 1] = sb[i] + 1ll * (tim + 1) * b[i + 1];
}
for(register int i = 2, tim = 3; i <= n; i += 2, tim += 4){
if(i <= n)sa[i] = sa[i - 1] + 1ll * tim * a[i];
if(i < n)sa[i + 1] = sa[i] + 1ll * (tim + 1) * a[i + 1];
}
for(register int i = 1; i <= n; i += 2){
sum = 0; int tim = (i - 1) * 2;
sum += sa[i - 1] + sb[i - 1];
sum += (ssa0[n] - ssa0[i - 1]) + 1ll * (tim - i) * (s0[n] - s0[i - 1]);
sum += ssb1[i] + 1ll * (tim + n - i) * (s1[n] - s1[i - 1]);
ans = max(ans, sum);
}
for(register int i = 1; i <= n; i += 2){
sum = 0; int tim = i * 2;
sum += sa[i] + sb[i];
sum += (ssb0[n] - ssb0[i]) + 1ll * (tim - i - 1) * (s1[n] - s1[i]);
sum += ssa1[i + 1] + 1ll * (tim + n - i - 1) * (s0[n] - s0[i]);
ans = max(ans, sum);
} cout << ans;
return 0;
}

D.Vasya And The Matrix

题目大意:给你一个\(n \cdot m\)的矩阵,告诉你每一行和每一列的异或和,让你求出一种合法解

题解:我们考虑直接对前\(n-1\)行只填第一个数,这个数等于每一行的异或和,也就是说前\(n-1\)

的每一行的后\(m-1\)列都填零,最后一行的第一个数等于第一列的异或和异或上第一列的前\(n-1\)行的每一个数

然后对于最后一行的后\(m-1\)个数都填的是对应的每一列的异或和,如果最后一行的所有数异或起来不等于最后一行的异或和就是无解,否则就是就是合法解

代码:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ull;

const int maxn = 3e2 + 5;

int n, m, c[maxn], r[maxn], mp[maxn][maxn];
int cnow[maxn], rnow[maxn];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main(){
//cout << (((1 << 30) - 1) << 1) + 1; 2147483647
n = read(); m = read();
for(register int i = 1; i <= n; i++)c[i] = read();
for(register int i = 1; i <= m; i++)r[i] = read();

for(register int i = 1; i < n; i++)
mp[i][1] = c[i], rnow[1] ^= c[i];
mp[n][1] = rnow[1] ^ r[1];
for(register int i = 2; i <= m; i++)
mp[n][i] = r[i], cnow[n] ^= r[i];
if((cnow[n] ^ mp[n][1]) != c[n])cout << "NO";
else {
cout << "YES" << endl;
for(register int i = 1; i <= n; i++){
for(register int j = 1; j <= m; j++)
cout << mp[i][j] << " ";
cout << endl;
}
}
return 0;
}

E.Rest In The Shades

题目大意:已知一个光源的纵坐标与横坐标的变化范围,现在\(x\)轴上有\(n\)条围栏(会挡住光线),并且第一象限中有\(q\)个点,问你点在起点移动到终点的过程中\(q\)个点中每个点处于阴影的时间。\(PS\):光源的移动速度为\(1\)单位每秒,

并且保证线段不相交

题解:我们换一种方法理解一下这个题目,其实这个题目要求的东西可以转化为,\(q\)个点中每个点和每条线段的左右端点连线后在光源的纵坐标的位置会得到\(n\)个投影,然后问这\(n\)个投影和光源移动的那个线段的重合部分有多长,因为我们得到的是\(n\)个不相交的投影,所以我们直接离散一下值域,然后二分一下光源移动的线段的左端点与右端点,把处于这个范围中间的完整的投影加上,再算一下两端不完全重合的投影所覆盖的长度即可,如图:

代码:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ull;

const int maxn = 2e5 + 5;
const double eps = 1e-11;

int n, Q;
struct Node{double l, r;}t[maxn];
double sum[maxn], y2, L, R;

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int lower(int l, int r, double x){
int mid = (l + r) / 2, ans = 0;
while(l <= r){
mid = (l + r) / 2;
if(t[mid].l > x)r = mid - 1;
else l = mid + 1, ans = mid;
} return ans;
}

inline bool equ(double x, double y){return fabs(x - y) <= eps;}

inline double getpos(double x2, double y2, double x3, double y3){
double k = 0, b = 0;
if(equ(x2, x3))return x2;
k = (y2 - y3) / (x2 - x3); b = y2 - k * x2;
return -b / k;
}

int main(){
//cout << (((1 << 30) - 1) << 1) + 1; 2147483647
y2 = read(); L = read(); R = read(); n = read();
for(register int i = 1; i <= n; i++){
t[i].l = read(); t[i].r = read();
sum[i] = sum[i - 1] + t[i].r - t[i].l;
} Q = read();

for(register int i = 1; i <= Q; i++){
double l = 0, r = 0, x = read(), y = read(), ans = 0;
l = getpos(x, y, L, y2); r = getpos(x, y, R, y2);
int posl = lower(0, n, l), posr = lower(0, n, r);
if(posr == 0)ans = 0;
else {
/*ans = min(r, max(l, t[posl].r)) - t[posl].l - fabs(l - t[posl].l);
if(posr > posl){
ans += max(r, t[posr].r) - t[posr].l - fabs(r - t[posr].r);
ans += sum[posr - 1] - sum[posl];
}*/
ans = sum[posr - 1] - sum[posl - 1];
ans -= (min(l, t[posl].r) - t[posl].l);
ans += max(r, t[posr].r) - t[posr].l - fabs(r - t[posr].r);
}
printf("%.15lf\n", ans * (y - y2) / y);
}
return 0;
}

F.Road Projects

题目大意:给你一棵树,有\(m\)个询问,每个询问有一个\(x\),问你再这棵树上的任意两个没有直接的遍相连的节点中间加上一条边权为 \(v\) 的边,从\(1\)号结点到\(n\)号节点的路径上边权和的最小值最大可以为多少

原题题面写的真TM辣鸡,又扯又说不清

题解:考虑这样一个事实,无论加的边的权值是多少我们每次都贪心选取相同的两个节点来加边肯定是最优的。

那么怎么求这一对节点呢,我们可以设\(d_1[x]\)\(1\)号结点到\(x\)号节点的权值,\(d_n[x]\)\(n\)号节点到\(x\)号结点的权值,如果在\(x,y\)中间加了一条边 \[ ans = min(d_1[n], min(d_1[x]+v+d_n[y],d_1[y]+v+d_n[x])) \] 如果\(d_1[x]+v+d_n[y] \leq d_1[y]+v+d_n[x]\) 等价于 \(d_1[x] - d_n[x] \leq d_1[y]-d_n[y]\) ,所以我们直接按照这个为比较的依据把所有的点都丢进一个\(vector\)中,然后\(sort\)一下,再呗所有点都丢进一个\(set\)中,这回用 \(d_n[x]\) 做为排序依据,然后顺序枚举一下,每个节点求一个相对于这个节点最优另一个节点即\(set.end() - 1\)等价于\(set.rbegin()\)(反向迭代器),

代码:

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 3e5 + 5;
const LL inf = (1ll << 60);

int n, m, cnt, head[maxn], pos[maxn];
LL d1[maxn], dn[maxn], minv = inf, maxv;
struct Graph{int to, nt, w;}e[maxn << 1];
vector<pair<LL, int> >o;
set<pair<LL, int> >s0;

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline void ini(int x, int y, int w){e[++cnt] = (Graph){y, head[x], w}; head[x] = cnt;}

inline void dfs(int now, int fa, LL *d, LL dis){
d[now] = dis;
for(register int i = head[now]; i; i = e[i].nt){
int v = e[i].to;
if(v == fa)continue;
dfs(v, now, d, dis + e[i].w);
}
}

int main(){
n = read(); m = read();
for(register int i = 1; i < n; i++){
int x = read(), y = read(), w = read();
ini(x, y, w); ini(y, x, w);
}
dfs(1, 1, d1, 0); dfs(n, n, dn, 0);
for(register int i = 1; i <= n; i++)
o.push_back(make_pair(d1[i] - dn[i], i));
sort(o.begin(), o.end());
for(register int i = 0; i < n; i++)
pos[o[i].second] = i + 1;
for(register int i = 1; i <= n; i++)
s0.insert(make_pair(dn[i], i));
for(register int i = 0; i < o.size(); i++){
int p = o[i].second;
s0.erase(make_pair(dn[p], p));
for(register int u = head[p]; u; u = e[u].nt){
int v = e[u].to;
if(pos[v] > pos[p])
s0.erase(make_pair(dn[v], v));
}
LL p0 = inf;
if(!s0.empty())
maxv = max(maxv, s0.rbegin() -> first + d1[p]);
for(register int u = head[p]; u; u = e[u].nt){
int v = e[u].to;
if(pos[v] > pos[p])
s0.insert(make_pair(dn[v], v));
}
}
for(register int i = 1; i <= m; i++){
int x = read();
printf("%lld\n", min(d1[n], maxv + x));
}
return 0;
}

G.Appropriate Team

题目大意:给你一个值域为\(10^{18}\)的序列\(a\), 和一个\(X,Y\),问你有多少对\(i,j\)满足存在一个\(V\), 使 \[ GCD(a_i,V) = X, LCM(a_j,V)=Y \] 特别的\(i,j\)可以相等

题解:由题意可知 $ V % X == 0, Y % V == 0 $ 所以如果\(Y \% X \neq 0\)则不存在\(V\)\(ans=0\)

否则 \[ X = \prod P_{i}^{p_{xi}}, Y = \prod P_{i}^{p_{yi}}, a_j = \prod P_{i}^{p_{aji}} \] 对于 \(GCD(x,y)\) 是将每个\(x,y\) 的素因子的个数取个\(min\)\[ GCD(x,y) = \prod P_i^{min(P_{xi}, P_{yi})} \]\(LCM(x,y)\) 则是取\(max\) \[ LCM(x,y) = \prod P_i^{max(P_{xi}, P_{yi})} \] 也就说如果对于\(GCD(a_i,V)\)的一个素因子\(P_i\)来说,如果\(P_{ai} > P_{xi}\), 那么\(P_{Vi} = P_{xi}\), 否则就无所谓

反过来如果对于\(LCM(a_j,V)\)的一个素因子\(P_i\)来说,如果 \(P_{ai} < P_{yi}\),那么\(P_{Vi}=P_{yi}\)

至此我们可以这样看,对于每一个素因子\(P_i\),设\(l=P_{xi},r=P_{yi}\) 如果\(P_{ai}==l||P_{aj}==r\)则存在这样的一个素因子, 特别的如果\(l==r\)也一定会存在一个这样的素因子,当对于每一个素因子都成立时就存在一个\(V\), 因为一个值域为\(10^{18}\)的数,至多有\(15\)不同的素因子, 所以我们可以直接搞一个二进制来表示一下对于每个素因子的状态,我们这样表示,如果对于一个素因子成立就把这一位设为\(1\),所以对于每个\(a_i\)他都有两个二进制\(l_i\)\(r_i\),最后要我们求的问题就可以转化为,从一个序列中取\(i,j\)使得\(l_i|r_j==(1<<15)-1\),但这样表示不太好看我们把不成立设为\(1\), 最后就是\(l_i \& r_i==0\) , 最后就是怎么算,官方题解给的是\(n\cdot2^n\),但是我并不会。我太菜辣

最后就是关于\(X,Y\)的素因数的分解,这里我用的是\(Pollard-rho\)算法,由于数据很毒瘤,这里一定要用龟速乘才能过,不然会爆

代码:

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ull;

const int maxn = 2e5 + 5;
const int inf = 1e9 + 7;

LL minv[1 << 16];
LL numx[15], numy[15];
LL n, a[maxn], x, y, A, B, facy[15000], ans;

inline LL read(){
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline LL gcd(LL x, LL y){return y == 0 ? x : gcd(y, x % y);}

inline LL mul(LL x, LL y, LL p){
LL cnt = 0;
while(y){
if(y & 1)cnt = (cnt + x) % p;
x = (x + x) % p; y >>= 1;
} return cnt;
}

inline LL ksm(LL x, LL k, LL p){
LL cnt = 1;
while(k){
if(k & 1)cnt = mul(cnt, x, p);
x = mul(x, x, p); k >>= 1;
} return cnt;
}

inline bool judge(LL a, LL p){
LL q = p - 1; int k = 0;
while(q % 2 == 0)
++k, q >>= 1;
LL v = ksm(a, q, p);
if(v == 1 || v == p - 1)return false;
while(k-- != 0){
v = mul(v, v, p);
if(v == p - 1)return false;
} return true;
}

inline bool miller_rabbin(LL p){
if(p == 2)return true;
if(p % 2 == 0)return false;
for(register int i = 1; i <= 60; i++){
LL a = rand() % (p - 1) + 1;
if(judge(a, p))return false;
} return true;
}

const int M = (1 << 7) - 1;

inline LL pollard_rho(LL n){
if (n % 2 == 0) return 2;
if (n % 3 == 0) return 3;
LL x = 0, y = x, t = 1, q = 1, a = (rand() % (n - 1)) + 1;
for (int k = 2;; k <<= 1, y = x, q = 1) {
for (int i = 1; i <= k; ++i) {
x = (mul(x, x, n) + a) % n;
q = mul(q, abs(x - y), n);
if (!(i & M)) {
t = gcd(q, n);
if (t > 1) break;
}
}
if (t > 1 || (t = gcd(q, n)) > 1) break;
}
if (t == n) {
t = 1;
while (t == 1) t = gcd(abs((x = ((mul(x, x, n) + a) % n)) - y), n);
}
return t;
}

inline void findfac(LL x){
if(x == 1)return;
if(miller_rabbin(x)){facy[++facy[0]] = x; return;}
LL p = x;
while(p >= x)p = pollard_rho(p);
findfac(p);
findfac(x / p);
}

// 0 133056495 897612484786617600
inline void dEBUG(LL *x, LL len){
cerr << "----------------------------------DEBUG----------------------------------" << endl;
for(register int i = 0; i <= len; i++)
cerr << x[i] << " ";
cerr << endl;
cerr << "----------------------------------DEBUG----------------------------------" << endl;
}

int main(){
srand(19260817);
n = read(); A = x = read(); B = y = read();
if(y % x != 0){cout << 0; return 0;}
for(register int i = 1; i <= n; i++)a[i] = read();
findfac(B);
sort(facy + 1, facy + 1 + facy[0]);
facy[0] = unique(facy + 1, facy + 1 + facy[0]) - facy - 1;
for(register int i = 1; i <= facy[0]; i++)
while(B % facy[i] == 0)B /= facy[i], numy[i]++;
for(register int i = 1; i <= facy[0]; i++)
while(A % facy[i] == 0)A /= facy[i], numx[i]++;
//dEBUG(facy, facy[0]);
//dEBUG(numx, facy[0]);
//dEBUG(numy, facy[0]);
for(register int i = 1; i <= n; i++){
if(a[i] % x != 0)continue;
int maskx = 0; LL T = a[i];
for(register int k = 1; k <= facy[0]; k++){
int p = 0;
if(numx[k] == numy[k])continue;
while(T % facy[k] == 0)T /= facy[k], p++;
maskx |= ((p > numx[k]) << (k - 1));
} minv[maskx]++;
}
for(register int i = 0; i < facy[0]; i++)
for(register int G = 0; G < (1 << facy[0]); G++)
if(G & (1 << i))minv[G] += minv[G ^ (1 << i)];
int MK = (1 << facy[0]) - 1;
for(register int i = 1; i <= n; i++){
if(y % a[i] != 0)continue;
int masky = 0; LL T = a[i];
for(register int k = 1; k <= facy[0]; k++){
int p = 0;
while(T % facy[k] == 0)T /= facy[k], p++;
masky |= ((p < numy[k]) << (k - 1));
}
ans += minv[masky ^ MK];
}
//dEBUG(minv, n); dEBUG(maxv, n);
cout << ans;
return 0;
}

Summary:读懂题目很重要,打代码之前想清楚为什么,不要不懂装懂,打完就完事了

Thinck Twice, Code once.