题目大意
唯首是瞻
时间限制：C/C++/Rust/Pascal 1 秒，其他语言 2 秒
空间限制：C/C++/Rust/Pascal 1024 MB，其他语言 2048 MB
Special Judge，64bit IO Format: %lld
在莫扎瑞拉的魔法国度里，一场召唤仪式出了大岔子。布朗尼本想召唤传说中的女法师加莱特完整降临，结果只有她的一颗头颅现身了。这颗漂浮的头颅却毫不在意，宣称道：“有头就够了！我要证明，光凭我的头脑就胜过你们的整副身躯。”
为了展示自己的智力，加莱特放出豪言：
“随便拿两个正整数来。只要你告诉我其中一个数的前 a 位、另一个数的前 b 位，我就能万无一失地说出它们乘积的前 c 位。那些看不见的低位，就像身体对于天才一样无关紧要。”
学院里最敏锐的数学家奥兰洁特立刻察觉到了其中的漏洞。但仅仅指出谬误还不够，加莱特要求给出一个具体的反例：“你要真这么聪明，就找出两对数来：它们的前几位分别相同，乘积的前几位却不同！”
奥兰洁特一时之间构造不出这样的例子，于是她来向你求助。
形式化地说，给定三个正整数 a、b、c，请构造两对正整数 (x1,y1) 与 (x2,y2)，满足以下条件：
-
在通常的十进制表示下（无前导零），x1 与 x2 都至少有 a 位，且二者的前 a 位完全相同；
-
同样地，y1 与 y2 都至少有 b 位，且二者的前 b 位完全相同；
-
乘积 x1⋅y1 与 x2⋅y2 都至少有 c 位，但二者的前 c 位不同。
每个测试点仅一行，包含三个整数 a、b、c（1≤a,b≤105，1≤c<a+b−1）。
输出四个整数 x1、y1、x2、y2，满足
10a−1≤x1,x2<105⋅105,10b−1≤y1,y2<105⋅105
且符合题目要求。这些整数均不能含有前导零。可以证明在给定约束下解总是存在的。
x1=1704 与 x2=1789 的前 2 位均为 17；y1=1313 与 y2=1346 的前 2 位均为 13。
而 1704×1313=2237352，其前 2 位为 22；1789×1346=2407994，其前 2 位为 24。两者的前 2 位不同，因此这是一组合法的构造。
思路讲解
claude 的神秘提示
固定住 x 的前 a 位之后，x 还剩多大的活动余地？把它量化出来。
答
x 只能写成 A⋅10t+r（0≤r<10t），即它的尾数被锁死在 [A,A+1) 内，相对活动幅度至多 A1≤10−(a−1)。y 同理。于是乘积的尾数活动幅度只有 101−a+101−b 量级。靠低位微调去顶动第 c 位是完全没希望的，尤其当 c=1 而 a,b 很大时。
尾数是什么
尾数就是把小数点挪到最高位后面得到的那个 [1,10) 里的实数。
1704=1.704×103，尾数是 1.704。
</div>
其实我们不是非常需要在意这个 C，因为无论这个 C 是多少，那么这个 C 都认为是 1 就可以了。
想通过改变数字的后缀（低位）来影响乘积的最高 c 位，必须利用什么机制？
答：必须利用连锁进位机制。当高位部分的乘积处于进位的临界状态（如形如 999…9 ）时，低位产生的微小增量才能不断向高位触发进位，进而使得最高位发生突变。为了制造上述的“进位临界状态”，两数的前缀 X 和 Y 应该构造成什么形式？
为了制造上述的**“进位临界状态”**，两数的前缀 X 和 Y 应该构造成什么形式？
答：需要让 X×Y 的结果尽可能呈现一连串的 9。一种极简的构造是令 X=10a−1（100..00，长度为 a），且 Y=10b−1（999...999，长度为这个这个 b）。此时 X×Y=10a+b−1−10a−1，其结果形如 99…900…0，恰好为连锁进位创造了绝佳条件。
确定了前缀后，两对数字 (x1,y1) 和 (x2,y2) 的后缀应如何选取，才能确保乘积的前 c 位一定不同？
答：将第一组数字的后缀全部填充为 0，此时乘积没有任何来自低位的增量，最高位保持为 9；将第二组数字的后缀全部填充为 9（即增量最大化），乘积加上这部分增量后会越过进位临界点，使得最高位进位变成 1。由于 c<a+b−1，前 c 位必定会因此改变。
1
2
3
4
5
| >>> 9999999999*10000099999
100000999979999900001
>>> 9999999999*10000000000
99999999990000000000
>>>
|
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
| import sys
def solve():
input_data = sys.stdin.read().split()
if not input_data:
return
a = int(input_data[0])
b = int(input_data[1])
c = int(input_data[2])
X_str = "1" + "0" * (a - 1)
Y_str = "9" * b
k = c + 5
x1_str = X_str + "0" * k
y1_str = Y_str + "0" * k
x2_str = X_str + "9" * k
y2_str = Y_str + "9" * k
print(f"{x1_str} {y1_str} {x2_str} {y2_str}")
if __name__ == '__main__':
solve()
|
AC代码
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84454600
源代码
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int a = 0;
int b = 0;
int c = 0;
while (scanf("%d %d %d", &a, &b, &c) == 3) {
const int N = a + b - 1;
string x1;
x1.reserve(a);
x1.push_back('1');
x1.append(a - 1, '0');
string y;
y.assign(N, '9');
string x2;
x2.reserve(a + b);
x2.push_back('1');
x2.append(a + b - 2, '0');
x2.push_back('2');
string out;
out.reserve(x1.size() + y.size() * 2 + x2.size() + 8);
out += x1;
out += '\n';
out += y;
out += '\n';
out += x2;
out += '\n';
out += y;
out += '\n';
fwrite(out.data(), 1, out.size(), stdout);
}
return 0;
}
|
心路历程（WA，TLE，MLE……）