Assssss!!
https://tioj.ck.tp.edu.tw/problems/1505
Description
現在有一個正整數構成的除法數列
$
x_1 / x_2 / x_3 / \dots / x_n
$
請問是否有一種加上括號的方法使得最後運算的結果是整數?
$2 \leq n \leq 10^5, 1 \leq x_i \leq 10^9$
Solution
加上括號之後每個數字會被放到分母或分子，想當然而放在分子的數字越多越好
可以發現$x_2$會恰好被放到分母一次，因此在最後他一定是當分母的
而我們可以構造出一個方法讓除了$x_2$最後當分母以外，其他數字都當分子
$$
(x_1 / (((x_2 / x_3) / x_4) / x_5 \dots)) = \frac{x_1 x_3 x_4 x_5 \dots x_n}{x_2}
$$
由於$x_2$最後一定會待在分母，只要檢查其他數字的乘積是否可以被$x_2$整除就好了
記得 long long 的問題
AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <cstdio>
inline char readchar() {
constexpr int B = 1<<20;
static char buf[B], *p, *q;
if(p == q && (q=(p=buf)+fread(buf,1,B,stdin)) == buf) return EOF;
return *p++;
}
inline int nextint() {
int x = 0, c = readchar();
while(c < '0') c = readchar();
while(c >= '0') x=x*10+(c^'0'), c=readchar();
return x;
}
signed main() {
int t = nextint();
while(t--) {
int n = nextint();
int res = nextint(), mod = nextint();
for(int i = 2; i < n; i++) res = 1LL * res * nextint() % mod;
puts(res ? "zzz..." : "Asssss!!");
}
}
|