ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190861 | #3390. 凯撒密码 | dianjin | 100 | 3ms | 1316kb | C++ | 2.3kb | 2023-10-07 18:40:27 | 2023-10-07 21:36:18 |
answer
#include <bits/stdc++.h>
using namespace std;
string S, T;
bool isnum[10005], ok = true;//isnum[i]:第i位是数字,字母和数字无矛盾
int alphaxun = -1, numxun = -1, xun[10005];
//字母的的最小循环长度, 数字的的最小循环长度, xun[i]: 第i个字符的最小循环长度
int exgcd(int a, int b, int &x, int &y){
if (!b){
x = 1, y = 0;
return a;
}else{
int d = exgcd(b, a%b, y, x);
y -= a/b * x;
return d;
}
}
int main(){
cin >> S >> T;
int n = S.size();
for (int i=0; i<n; ++i){
if (isalpha(S[i])){
if (!isalpha(T[i])) {//字母变数字,矛盾!
ok = false;
break;
}else{
xun[i] = (T[i] - S[i] + 26) % 26;
}
}else{//是数字
isnum[i] = true;
if (!isdigit(T[i])) {//数字变字母,矛盾!
ok = false;
break;
}else{
xun[i] = (T[i] - S[i] + 10) % 10;
}
}
}
if (!ok){
cout << "IMPOSSIBLE\n";
}else{
for (int i=0; i<n; ++i){
if (isnum[i]){
if (numxun == -1) numxun = xun[i];//第一次出现数字
else{
if (numxun != xun[i]){//数字的循环节不一致,矛盾!
ok = false;
break;
}
}
}else{
if (alphaxun == -1) alphaxun = xun[i];//第一次出现字母
else{
if (alphaxun != xun[i]){//字母的循环节不一致,矛盾!
ok = false;
break;
}
}
}
}
if (!ok){
cout << "IMPOSSIBLE\n";
} else{
if (alphaxun == numxun) cout << alphaxun << endl;
else if (alphaxun == -1){//没有出现字母,这种情况不要漏!!!
cout << numxun % 10 << endl;
}else if (numxun == -1){//没有出现数字,这种情况不要漏!!!
cout << alphaxun % 26 << endl;
}else{
//求alphaxun+26*x == numxun+10*y的最小非负整数解
//利用扩展欧几里德算法求 26*x -10*y = numxun-alphaxun的最小非负整数解
int x, y;
exgcd(26, -10, x, y);
//26与-10的最大公约数是2
if ((numxun-alphaxun) % 2 != 0) cout << "IMPOSSIBLE\n";
else {
int b = (numxun-alphaxun) / 2;//倍数
x *= b, y *= b;
while (x < 0 || y < 0) x += 5, y += 13;
while (x-5 >= 0 && y-13 >= 0) x -= 5, y -= 13;
cout << alphaxun+26*x << endl;
}
}
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1192kb
input:
a 0
output:
IMPOSSIBLE
result:
ok single line: 'IMPOSSIBLE'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1228kb
input:
c x
output:
21
result:
ok single line: '21'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1228kb
input:
8 3
output:
5
result:
ok single line: '5'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1236kb
input:
097 097
output:
0
result:
ok single line: '0'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1232kb
input:
135409 357621
output:
2
result:
ok single line: '2'
Test #6:
score: 10
Accepted
time: 1ms
memory: 1308kb
input:
ulhpnmrkblwafxapsldccdplmqukqlxwixjtleoirjyyivdguyiffnvunoxconwjvovmqluhyypgfkmdvgpzjuepkwjdoniezcli...
output:
21
result:
ok single line: '21'
Test #7:
score: 10
Accepted
time: 1ms
memory: 1308kb
input:
ijvxljtolmgjndlwoyjjttakhzvzmihjdhkyfnafwrpeuiuiurusvsnugviqzouvuxalhxmxhclxdzrxylbzsmdruqpnvagkninp...
output:
13
result:
ok single line: '13'
Test #8:
score: 10
Accepted
time: 1ms
memory: 1316kb
input:
lb3zc66k080upg8dfv18jctk0sejke93251mw9f3642u1x7889s5y38wdv39391v3gptt6656248xw576z2w27gh9t3wh5j634lg...
output:
22
result:
ok single line: '22'
Test #9:
score: 10
Accepted
time: 0ms
memory: 1316kb
input:
h18855603165ay78uft01r1i89sx9o1z6d1h0nd2l8f28xe05571r64vjeofr32453571pa1z9x47dpg5k3uw2027lx4270g4xyh...
output:
98
result:
ok single line: '98'
Test #10:
score: 10
Accepted
time: 0ms
memory: 1312kb
input:
2c3hoz6dbcggcjjf665nqfcy3w2yoej1lyr1j523230e2q228b6vn96gsuq1sustb1269uiyrk6y3gi883f789rro7nomg9776w1...
output:
129
result:
ok single line: '129'
Extra Test:
score: 0
Extra Test Passed