Интересная задачка на математику

[Demius]

Недавно наткнулся на следующую задачку:

Практически каждый уважающий себя программист знает, что для полного успеха зачастую мало написать программный продукт, его также успешно надо уметь продать, и тем более также успешно защитить от взлома, а соответственно и от несанкционированного распространения.

Многие годы основным способом защиты программного обеспечения от незаконного распространения было использование, так называемого, активационного ключа. Вся проблема заключалась и заключается в том, что зачастую используется статический ключ, то есть активационный ключ для конкретного программного продукта не зависит ни от каких параметров и всегда является неизменным.

Знаменитая компания "Gold&Silver Soft" решилась на революционный шаг – было решено разработать принципиально новый способ динамической генерации активационного ключа. В данном алгоритме ключ зависит от времени и меняется каждую минуту, что существенно затрудняет взлом.

Будем считать, что активационным ключом является обычное целое положительное число. В данной версии алгоритма значение ключа на следующей минуте целиком и полностью зависит от значения ключа в текущий момент. Если в данный момент ключ равен N, то через минуту он будет равен N + S(N), где S(N) – это число, называемое контрольной суммой числа N и равняется количеству единиц в двоичной записи числа N. То есть если N = 6, то в следующую минуту значение ключа будет равно 8, если быть точнее, то N’ = N + S(N) = 6 + S(6) = 6_10 + 110_2 = 8.

Будем считать, что на данный момент времени значение ключа равно N, вашей задачей является вычислить значение ключа через K минут.

Для K = 1, решение очевидно, но ограничения на N и K - N (1 ≤ N ≤ 2*10^9) и K (1 ≤ K ≤ 2*10^9).

Как решить эту задачу при данных ограничениях?

P.S.: ссылка на задачу Временной ключ-2

[challengerr]

int intp(unsigned int x){int h, I; unsigned int t=x; for(i=0, j=0; i<32;i++) {t=x<<i; t>>=31; if(t==1) j++; } return j;}
int main(){ int n=2000000000; int k=1; int i; for(i=0; i<k;i++) n+=intp(n);} return 0;}

Время исполнения имеет значение?

[Poma][a]

Сообщение от challengerr

int intp(unsigned int x){int h, I; unsigned int t=x; for(i=0, j=0; i<32;i++) {t=x<<i; t>>=31; if(t==1) j++; } return j;}
int main(){ int n=2000000000; int k=1; int i; for(i=0; i<k;i++) n+=intp(n);} return 0;}

Время исполнения имеет значение?

(Время: 1 сек. Память: 16 Мб Сложность: 80%)

[challengerr]

//решение неправильное. идея в том, чтобы разбить n на части по 24 бита и 8 бит. Предположительно, увеличение n  изменяет только 8  бит в n
int gl, gk, gc;
void intp(unsigned int x){int i, m; unsigned int t=x; for(i=0, m=0; i<32;i++) { t= x<<i; t>>=31; if (i<=23 && t==1) gl++; if(i>23){ if(t==1) gk++; m++; gc|=t; gc<<=m;}}}
int charp(unsigned char x){ int i, j; for(i=0, j=0; i<8;i++) { if (((x<<i)>>7) ==1) j++;} return j;}
int main(){ int n= 2000000000; int k= 2000000000; int i; intp(n); gc+= gl+ gk; for(i=0; i<k; i++) gc += gl + charp(gc); return 0;}

s(n) <= 32; n увеличивается незначительно. М.б это нужно учесть?

[Poma][a]

увеличивается незначительно

Или уменьшается