UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190861#3390. 凯撒密码dianjin1003ms1316kbC++2.3kb2023-10-07 18:40:272023-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;
}

Details

小提示:点击横条可展开更详细的信息

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