洛谷 P1050 [NOIP2005 普及组] 循环 AC

题目描述

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。

众所周知，22 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…2,4,8,6,2,4,8,6… 我们说 22 的正整数次幂最后一位的循环长度是 44（实际上 44 的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：

\def\arraystretch{1.5}

数字23456789​循环2,4,8,63,9,7,14,6567,9,3,18,4,2,69,1​循环长度44211442​​

这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数 nn 的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？

注意：

1. 如果 nn 的某个正整数次幂的位数不足 kk，那么不足的高位看做是 00。
2. 如果循环长度是 LL，那么说明对于任意的正整数 aa，nn 的 aa 次幂和 a+La+L 次幂的最后 kk 位都相同。

输入格式

共一行，包含 22 个整数 nn 和 kk。nn 和 kk 之间用一个空格隔开，表示要求 nn 的正整数次幂的最后 kk 位的循环长度。

输出格式

一个整数，表示循环长度。如果循环不存在，输出 -1−1。

输入输出样例

输入 #1复制

32 2

输出 #1复制

4

说明/提示

【数据范围】

对于 30 \%30% 的数据，满足 k \le 4k≤4；
对于100 \%100% 的数据，满足 1 \le n < {10}^{100}1≤n<10100，1 \le k \le 1001≤k≤100。

【题目来源】

NOIP 2005 普及组第四题

#include 
using namespace std;
const int N = 18;
const int M = 1e4+10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x
vector<int> mul(vector<int> A, vector<int> B,int r){
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i ++ )
        for (int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];
    for (int i = 0, t = 0; i < C.size() || t; i ++ ){
        t += C[i];
        if (i >= C.size()) C.push_back(t % 10);
        else C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && !C.back()) C.pop_back();
    while(C.size()>r)C.pop_back();
    return C;
}
signed main() {
    fast
    string s; cin >> s;
    vector<int> v;
    int k; cin >> k;
    int n = s.size();
    for (int i = n - 1; i >= n - k; i--)v.push_back(s[i] - '0');
    vector<int> v1 = v;
    vector<int> v2 = v;
    vector<int> ans;
    ans.push_back(1);
    for (int i = 0; i < k; i++) {
        if(mul(v,v2,k)[i]==v[i])continue;
        int u=1;
        do{
            v2=mul(v1,v2,k),++u;
            if(u>10){cout<<-1<return 0;}
        }while(mul(v,v2,k)[i]!=v[i]);
        v1=v2;
        vector<int>v3;
        v3.push_back(u);
        ans=mul(ans,v3,1e9);
    }
    for(int i=ans.size()-1;i>=0;i--)cout<
    return 0^0;
}