【题解】循环

系统管理员 2021-11-11 04:01 327阅读 0赞

# 题目描述 #

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

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

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

注意：

1． 如果$n$的某个正整数次幂的位数不足$k$，那么不足的高位看做是$0$。

2． 如果循环长度是$L$，那么说明对于任意的正整数$a$, $n$的$a$次幂和$a + L$次幂的最后$k$位都相同。

# 输入格式 #

一行，包含$2$个整数$1 \\leqslant n < 10 ^ \{100\}$和$1 \\leqslant k \\leqslant 100$，$n$和$k$之间用一个空格隔开，表示要求$n$的正整数次幂的最后$k$位的循环长度。

# 输出格式 #

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

# 输入样例 #

32 2

# 输出样例 #

# 题解 #

容易想到，如果最后$i$位的循环长度为$L\_\{i\}$，最后$i + 1$位的循环长度为$L\_\{i + 1\}$，则$L\_\{i\} | L\_\{i + 1\}$。

我们设最后$i$位要乘$a^\{L\_\{i\}\}$才能重复，则对于最后$i + 1$位，每次都乘上$a^\{L\_\{i\}\}$，当乘上$cnt$次才重复时，则$L\_\{i+1\} = L\_\{i\} \\times cnt$。

注意，如果$a^\{L\_\{i\} + 1\}$的最后$i$位与$a$的最后$i$位相同，那也要输出$-1$。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    #define MAX_LEN (100 + 5)
    
    using namespace std;
    
    int k;
    
    struct BigNumber
    {
        int bit[MAX_LEN + MAX_LEN], len;
        
        BigNumber()
        {
            memset(bit, 0, sizeof bit);
            len = 1;
            return;
        }
        
        BigNumber operator = (char * s)
        {
            memset(bit, 0, sizeof bit);
            len = strlen(s + 1);
            for(register int i = 1; i <= len; ++i)
            {
                bit[i] = s[len - i + 1] - '0'; 
            }
            return *this;
        }
        
        BigNumber operator = (int num)
        {
            memset(bit, 0, sizeof bit);
            len = 0;
            do
            {
                bit[++len] = num % 10;
                num /= 10; 
            }
            while(num);
            return *this;
        }
        
        inline bool notZero()
        {
            return len > 1 || bit[1];
        }
        
        friend BigNumber operator + (BigNumber a, BigNumber b)
        {
            if(a.len < b.len) a.len = b.len;
            for(register int i = 1; i <= a.len; ++i)
            {
                a.bit[i] += b.bit[i];
            }
            for(register int i = 1; i <= a.len && i <= k; ++i)
            {
                if(a.bit[i] >= 10)
                {
                    if(i == a.len) ++a.len;
                    ++a.bit[i + 1];
                    a.bit[i] -= 10;
                } 
            }
            if(a.len > k) a.bit[a.len--] = 0;
            return a;
        }
        
        friend BigNumber operator += (BigNumber & a, BigNumber b)
        {
            return a = a + b;
        }
        
        friend BigNumber operator * (BigNumber a, BigNumber b)
        {
            BigNumber c;
            c.len = a.len + b.len - 1;
            if(c.len > k) c.len = k;
            for(register int i = 1; i <= a.len; ++i)
            {
                for(register int j = 1; j <= b.len && i + j - 1 <= k; ++j)
                {
                    c.bit[i + j - 1] += a.bit[i] * b.bit[j];
                }
            }
            for(register int i = 1; i <= c.len && i <= k; ++i)
            {
                if(c.bit[i] >= 10)
                {
                    if(i == c.len) ++c.len;
                    c.bit[i + 1] += c.bit[i] / 10;
                    c.bit[i] %= 10;
                } 
            }
            if(c.len > k) c.bit[c.len--] = 0;
            return c;
        }
        
        friend BigNumber operator *= (BigNumber & a, BigNumber b)
        {
            return a = a * b;
        }
        
        void Write()
        {
            for(register int i = len; i; --i)
            {
                printf("%d", bit[i]);
            }
            return;
        }
    };
    
    BigNumber a;
    int f[15];
    BigNumber dp[MAX_LEN];
    
    int main()
    {
        char s[MAX_LEN];
        scanf("%s%d", s + 1, &k);
        a = s;
        dp[0] = 1;
        BigNumber res, p, tmp;
        tmp = a;
        for(register int i = 1; i <= k; ++i)
        {
            memset(f, 0, sizeof f); 
            p = tmp;
            tmp = 1;
            res = a;
            f[res.bit[i]] = 1;
            while(f[res.bit[i]] < 2)
            {
                tmp *= p;
                res *= p;
                ++f[res.bit[i]];
                dp[i] += dp[i - 1];
            }
            if(res.bit[i] != a.bit[i]) return cout << -1, 0;
        }
        dp[k].Write();
        return 0;
    }

参考程序

转载于:https://www.cnblogs.com/kcn999/p/11184561.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/f9a871bb8f464259a35431cc3025f63f.png