Как проверить делимость чисел из последовательности 1,11,111,...,11..1 на их порядковые номера?

Question

[Абубакр Мирзоев]

Дана последовательность из чисел (последовательность из единиц): 1, 11, 111, ..., 11..1. (до N)
Требуется определить делимость числа на его порядковый номер и записать в массив 0 или 1.
Я написал решение, но с проблемами.
Вот мой код:

#include <iostream>
#include <string>
#include <stdlib.h>
#include <sstream>
 
using namespace std;
 
template <typename T>
string toStr(T val){
    ostringstream oss;
    oss<< val;
    return oss.str();
}
 
int main()
{
//-----------------ВВОД ВЫВОД ПОСЛЕДОВАТЕЛЬНОСТЕЙ------------------
    int i,j,N;
    cout<<"Vvedite N:";
    cin>>N;
    cout<<endl;
 
    string *a=new string[N];
    int *is_div = new int[N];
 
    a[0]="1";
    for(i=1;i<N;++i)
        for(j=0;j<=i;++j)
            a[i]+='1';
    for(i=0;i<N;++i)
        cout<<a[i]<<endl;
//--------АЛГОРИТМ ДЕЛЕНИЯ--------------------------
    string x;
    int dlina_a,x_ch,ost,result_ost;
 
    for(i=0;i<N;++i){
//N_a - Номер числа, kolpos_N - Кол.-во цифр в числе, dlina_a - длина числа
            int N_a=i+1,N1=N_a,kolpos_N=0,dlina_a=N_a;
 
            while(N1>0){
                N1=N1/10;
                kolpos_N++;
            }
        while(dlina_a>0){
            x=a[i].substr(0,kolpos_N);
                dlina_a-=kolpos_N;
                    a[i]=a[i].erase(0,kolpos_N);
            x_ch = atoi(x.c_str());
            if(x_ch<N_a){
                x+=a[i].substr(0,1);
                a[i]=a[i].erase(0,1);
                dlina_a-=1;
            }
            ost = x_ch%N_a;
            if(ost==0 && dlina_a>0)
                continue;
            else if(ost!=0 && dlina_a>0)
                a[i]=toStr(ost)+a[i];
            else
                result_ost=ost;
        }
        if(result_ost)
            is_div[i]=1;
        else
            is_div[i]=0;
    }
    for(int k=0;k<N;++k)
        cout<<is_div[k]<<"\n";
    return 0;
}

В массив is_div должны сохраняться ответы 0-"нет" или 1-"да".
У меня выводит, что 1%1=0, 11%2=1, 111%3=1 - ошибка. т.е. после первого цикла в is_div сохраняются только единицы. Помогите решить задачу.
Вот что у меня получается:

Comments

[Владимир Мартьянов]

Используйте отладчик

Answer 1

[Mrrl]

Если N небольшое (скажем, не больше 100000), то можно так:

char *A=new char[N+1];
  for(int n=1;n<=N;n++){
    int a=0;
    for(int b=0;b<n;b++) a=(10*a+1)%n;
    A[n]=!a;
  }

При больших N нужно пользоваться аналогом быстрого возведения в степень.
Получается, что кроме 3 и 37, в числах оказываются такие простые делители, как 163, 757, 1999, 9397... Не понимаю, откуда они берутся.
UPD.
757 - делитель 10^27-1
163 и 9397 - делители 10^81-1
1999 - делитель 10^999-1

Comments

[Абубакр Мирзоев]

Спасибо, MRRL!

Answer 2

[iSergios]

Простите мне мой питон:

def func(n):
    result=[]
    m=[int('1'*x) for x in range(1,n+1)]
    for c in m:
        result.append(int(c%(m.index(c)+1)==0))
    return result

Где n - число элементов в последовательности.
Если добавить в функцию вывод заданной последовательности, получим:

>>> func(10)
[1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111]
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0]