Подсчитать больше 8 автоморфных чисел

Question

Задание: Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 5^2 = 25, 25^2 = 625. Автоморфные числа существуют в системе счисления, основание n которой не должно быть простым числом или его степенью (n = 6,10,12,14…). Составьте алгоритм нахождения k автоморфных чисел в заданной системе счисления.

В 10-ричной сс программа быстро считает первые 8 чисел до числа 9376, затем не отвечает около минуты и выдает отрицательные значения. Было предположение, что произошло превышение диапазона int, заменила все переменные на long long, но это ничего не изменило. Что-то подобное происходит и в других сс.

#include <iostream>
#include <stdbool.h>
#include <stdlib.h>

// Является ли число простым или его степенью
bool isPrime(int num)
{
    int ct = 0;
    int dnum = num;
    if (num > 1)
    {    
        // в цикле перебираем числа от 2 до n - 1
        for (int i = 2; i < num; i++)
            if (num % i == 0) {// проверяем, есть ли у числа делитель 
                while (dnum > 1) {
                    dnum /= i;
                    ct += 1;
                }
                if (num == pow(i, ct)) 
                    return 1;
                
                else return 0;
            }
        return 1;
    }
    else
        return 0;
}

// Проверяет, является ли число автоморфным в заданной сс
bool isAutomorphic(int num, int radix)
{
    long long p = num * num;
    while (num && p % radix == num % radix) {
        p /= radix;
        num /= radix;
    }
    return (num == 0);
}

// Перебирает числа в поисках автоморфного
void defineNumers(int radix, int count) {
    long long check = 0;
    long long i = 1;
    char snum[] = {"000000000000000000000000000"};
    while (check < count) {

        // Проверка основания на соответсвие условию
        if (isAutomorphic(i, radix)) {
            check++;

            // Перевод в нужную систему счисления
            _itoa_s(i, snum, radix);
            printf_s("%s\n", snum);
        }
        i++;

    }

}

int main()
{
    long long n, k;
    printf_s("Enter a radix that must not be a prime or its power:\n");
    scanf_s("%d", &n);
    if (isPrime(n)) {
        printf_s("Automorphic numbers don't exist\n");
        exit(-1);
    }    
    printf_s("Enter the number of automorphic numbers\n");
    scanf_s("%d", &k);
    defineNumers(n, k);
}

Answer 1

Ну, ограничиваясь десятеричной системой и числами, влазящими в unsigned long long, т.е. без длинной арифметики, мы можем получить не более 9-значных автоморфных чисел.

Ваш метод мне не очень нравится, проще воспользоваться теоремами отсюда и написать вот такой код:

int main(int argc, char * argv[])
{
    unsigned long long x = 5, v = 6, y = x*x, w = v*v, tenn = 10;
    for(unsigned long long n = 1; n <= 9; ++n, tenn *= 10)
    {
        unsigned long long a = (y/tenn)%10;
        unsigned long long aa = a * tenn;
        unsigned long long z = x + aa;
        y += (z+x)*aa;
        x = z;
        a = (w/tenn)%10;
        if (a != 0) a = 10 - a;
        aa = a * tenn;
        z = v + aa;
        w += (z+v)*aa;
        v = z;
        printf("N = %lld  x5 = %lld  x6 = %lld  sum = %lld\n",n,x,v,x+v);
    }
}

Можно работать и дальше, тут даже длинная арифметика достаточно простая...

P.S. Зато как это легко и просто на Python'е с его суперцелыми... :)

x = 5
v = 6
y = x*x 
w = v*v
tenn = 10

for n in range(1,102):
    a = (y//tenn)%10
    aa = a * tenn
    z = x + aa
    y += (z+x)*aa
    x = z
    a = (w//tenn)%10
    if (a != 0):
        a = 10 - a
    aa = a * tenn
    z = v + aa
    w += (z+v)*aa
    v = z
    print("N = ",n," x5 = ",x, "  x6 = ",v," sum = ",x+v)
    tenn *= 10

И как вишенка на торте — тысячезначные автоморфные

12781254001336900860348890843640238757659368219796
26181917833520492704199324875237825867148278905344
89744014261231703569954841949944461060814620725403
65599982715883560350493277955407419618492809520937
53026852390937562839148571612367351970609224242398
77700757495578727155976741345899753769551586271888
79415163075696688163521550488982717043785080284340
84412644126821848514157729916034497017892335796684
99144738956600193254582767800061832985442623282725
75561107331606970158649842222912554857298793371478
66323172405515756102352543994999345608083801190741
53006005605574481870969278509977591805007541642852
77081620113502468060581632761716767652609375280568
44214486193960499834472806721906670417240094234466
19781242669078753594461669850806463613716638404902
92193418819095816595244778618461409128782984384317
03248173428886572737663146519104988029447960814673
76050395719689371467180137561905546299681476426390
39530073191081698029385098900621665095808638110005
57423423230896109004106619977392256259918212890625

и

87218745998663099139651109156359761242340631780203
73818082166479507295800675124762174132851721094655
10255985738768296430045158050055538939185379274596
34400017284116439649506722044592580381507190479062
46973147609062437160851428387632648029390775757601
22299242504421272844023258654100246230448413728111
20584836924303311836478449511017282956214919715659
15587355873178151485842270083965502982107664203315
00855261043399806745417232199938167014557376717274
24438892668393029841350157777087445142701206628521
33676827594484243897647456005000654391916198809258
46993994394425518129030721490022408194992458357147
22918379886497531939418367238283232347390624719431
55785513806039500165527193278093329582759905765533
80218757330921246405538330149193536386283361595097
07806581180904183404755221381538590871217015615682
96751826571113427262336853480895011970552039185326
23949604280310628532819862438094453700318523573609
60469926808918301970614901099378334904191361889994
42576576769103890995893380022607743740081787109376

:)

БЛОГ НА HUSL

Подсчитать больше 8 автоморфных чисел

Ответы (1 шт):