Решение задачи №391 «Взлом хеш-функции» с ACMP

Условие задачи

В некоторых задачах защиты информации используются так называемые хеш-функции. Одним из важнейших классов хеш-функций являются так называемые полиномиальные хеш-функции.

Пусть дана строка S = s1s2 ... sl, состоящая из цифр от 0 до 9. Тогда значение полиномиальной хеш-функции p(S, x, m) вычисляется следующим образом:

Хеш-функция

(a mod b обозначает остаток от деления числа a на число b). Например, пусть S = 0123, тогда p(S, 2, 5) = (0 ∙ 1 + 1 ∙ 2 + 2 ∙ 4 + 3 ∙ 8) mod 5 = 4.

Одним из способов применения хеш-функций является хранение паролей. Часто бывает так, что пароли приходится хранить в незащищенной таблице базы данных, поэтому вместо них хранят хеш-функции от них. При проверке пароля вычисляется хеш-функция от введенной строки и сравнивается со значением, хранящимся в таблице.

Ваша задача состоит в том, чтобы по заданным числам x, m, L и v найти строку S из цифр от 0 до 9 длины L, значение полиномиальной хеш-функции p(S, x, m) равно v.

Входные данные
Входной файл INPUT.TXT содержит четыре целых числа: x (x – простое число, 5 ≤ x ≤ 100), m (m является степенью двойки, 1 ≤ m ≤ 256), L (10 ≤ L ≤ 100) и v (0 ≤ v ≤ m-1).

Выходные данные
В выходной файл OUTPUT.TXT выведите искомую строку или NO SOLUTION, если такой строки не существует. Если решений несколько, выведите любое.

Решение на C++


    #include<iostream>

#include<string>

using namespace std;

string nxt(string s)

	{string t=s;int i;

	i=s.size()-1;

	while(i>=0&&s[i]=='9'){s[i]='0';--i;}

	if(i>=0)t[i]++;

	return t;}

int p(string s,int x,int m)

    {int h=0,i,r=1,l=s.size();

	for(i=0;i<l;++i)

		{h=(h+(s[i]-'0')*r)%m;

		 r=(r*x)%m;}

	return h; }

int main(){

	int m,x,L,v,i;string s="",t;

	cin>>x>>m>>L>>v;

	for(i=0;i<L;++i)s+='0';

	t=s;

	while(p(t,x,m)!=v)

		{t=nxt(t);

		if(t==s){cout<<"NO SOLUTION";return 0;}}

	cout<<t;	

	return 0;}

Условия задач взяты с сайта acmp.ru