보급 그룹 순환

제목.
순환 하 다.
알고리즘
(고밀도, 수학, 수론, 전달) O (10k 3) O (10k ^ 3) O (10k3)
인용 1: 전 k + 1 k + 1 k + 1 비트 의 모든 순환 절 길 이 는 반드시 전 k k k 비트 순환 절 길이 의 부분 집합 입 니 다.
증명:
4. 567917. 만약 에 앞의 k k k 비트 가 모두 다르다 면 앞의 k + 1 k + 1 k + 1 비트 도 반드시 다르다
인용 2: 최소 순환 절의 길이 가 t t t 라 고 가정 하면 모든 순환 절의 길 이 는 반드시 t t 의 정수 배 이다.
증명:
4.5567917. 순환 절 길이 r r r r 가 t t t 의 배수 가 아니 라 고 가정 하면 령 p = r   m o d   t p = r \ \, mod \, t p = rmodt, p < t p < t p < t, 그리고 임의의 정수 a a a 에 대해 서 는 모두 n a + n a + r − n a + r − t - t, n a + r − t - t, n a + r − t - 2 t.................. 2t..................................................................10 ^ k na..............................................................................................
따라서 우 리 는 어 릴 때 부터 한 명 씩 앞 k k k 비트 의 순환 절 길 이 를 내 놓 을 수 있다.
전 k 0 k 를 구 했다 고 가정 합 니 다.0 k0 비트 의 순환 절 길이 t 0 t0 t0, 그럼 우리 가 구하 기 전에 k 0 + 1 k0 + 1 k0 + 1 비트 의 순환 절 길 이 는 n 을 매 거 하기 만 하면 됩 니 다.× n t 0 , n × n 2 t 0 , n × n 3 t 0 , … , n × n 10 t 0 n×n^{t_0},n×n^{2t_0},n×n^{3t_0},…,n×n^{10t_0} n×nt0​,n×n2t0​,n×n3t0​,…,n×n10t 0 이 n n n 과 같 으 면 됩 니 다.
앞 k 0 k0 k0 위 는 고정 불변 입 니 다. k 0 + 1 k 만 있 습 니 다.0 + 1 k0 + 1 비트 가 변 하기 때문에 최대 10 가지 선택 만 가능 합 니 다.
시간 복잡 도
모두 k k k 비트 를 전달 해 야 합 니 다. 매번 전달 할 때 최대 10 개 를 매 거 해 야 합 니 다. 매 거 할 때마다 높 은 정밀도 의 곱셈 을 사용 합 니 다.
여기 서 고밀도 곱셈 은 FFT 로 가속 하지 않 았 기 때문에 시간 복잡 도 는 O (10k 3) O (10k ^ 3) O (10k3) 입 니 다.
C + + 코드

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int m;
int nums[N], power[N]; // power   n^L_{k-1}

//      
void mul(int c[], int a[], int b[])
{
    static int temp[N];
    memset(temp, 0, sizeof temp);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            if (i + j < m)
                temp[i + j] += a[i] * b[j];

    for (int i = 0, t = 0; i < m; i++)
    {
        t += temp[i];
        temp[i] = t % 10;
        t /= 10;
    }

    memcpy(c, temp, sizeof temp);
}

//        
void mul(int c[], int a[], int b)
{
    for (int i = 0, t = 0; i < m; i++)
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
}

int main()
{
    string str;
    cin >> str >> m;
    for (int i = 0, j = str.size() - 1; j >= 0; i++, j--)
        nums[i] = str[j] - '0'; //        nums 

    memcpy(power, nums, sizeof nums);

    int per[N] = {1}; // per     
    int pn[N], p1[N];// pn n*n^iL_{k-1}，p1 1*n^iL_{k-1}
    for (int k = 1; k <= m; k++)
    {
        memcpy(pn, nums, sizeof pn); //   n copy pn 
        memset(p1, 0, sizeof p1); // p1   
        p1[0] = 1;

        //             
        int r = 0;
        while (r <= 10)
        {
            mul(pn, pn, power); // pn = pn * power
            mul(p1, p1, power); // p1 = p1 * power
            r++;
            if (pn[k - 1] == nums[k - 1])
                break;
        }

        memcpy(power, p1, sizeof p1);

        if (r > 10)
        {
            memset(per, 0, sizeof per);
            per[0] = -1;
            break;
        }

        mul(per, per, r); // per = per * r
    }

    int k = m;
    while (!per[k])
        k--; //    0  

    while (k >= 0)
        cout << per[k--]; //           

    return 0;
}