INOI 2015 – Периодические строки ⇐ C++

[Anonymous]

Вопрос: https://www.codechef.com/INOIPRAC/problems/INOI1502
Вот что я подумал:

• Имейте функцию f(n), которая находит факторы n
• Если найден фактор i, вызовите f(i)
• для каждого значения n функция также вычисляет количество непериодических строк, равное 2^n - (значение, возвращаемое каждым из вызовов функции)
• возвращает количество непериодических строк и сохраняет это число в массиве для предотвращения

Затем я просто вызываю функция, f(n) по модулю n, чтобы получить результат.
Она работает для меньших значений, но не для больших.
Например, когда n=35 и m=99999989
Мой код на данный момент:

Код: Выделить всё

#include 
#include 
using namespace std;
int arr[150100];
int ans[150100];
int check(int n){
if(arr[n]>0){
return arr[n];
}
else if(n == 1){
arr[n] = 2;
return 2;
}
if(n==2){
arr[n] = 2;
return 2;
}
for(int i =1 ;i>n>>m;
for(int i=0;i

Подробнее здесь: [url]https://stackoverflow.com/questions/47962737/inoi-2015-periodic-strings[/url]