对余数乘方的深刻理解

此题需要对余数乘方的深刻理解

解题思路:
   总体思路:
   N位的循环节长度是 N-1的循环节长度的倍数.
   所以,
   1位的长度是5的话,
   2位的长度就一定是5的倍数,比如25
   3位的长度就一定是25的倍数,比如75
   要注意的是,1,2,3位的循环节长度可能一致,比如长度都是5,这个是符合规律的
   
   测试高位的循环节,可以每间隔低位循环节的次数测试一次,
   最多测试10次,就应该出现循环,否则就是没有循环.
   
   在低次出现循环节时候,记录此时的结果,
   后面可以直接乘此结果,相当于次方增加[低位循环节长度的]次数.

参考代码:

#include<stdio.h>
#include <string.h> 

//小端格式 value 增加一个值 addv
void char_add(char* value,char addv, int len)
{
    for(int i=0; i0; i++)
    {
        int temp = value[i]+addv;
        value[i] = temp%10;
        addv = temp/10;
    }
}

//product = (yushu*n) % pow(10,k); 小端格式的数据
void calculate(char* yushu, char* n, char* product, int k)
{
    memset(product,0,sizeof(char)*k);
    char temp;
    
    for(int i = 0; i < k; i++)
    {
        for(int j = 0; j < k; j++)
        {
            if(i+j<k)
            {
                temp = yushu[i] * n[j];
                char_add(product+i+j, temp, k-i-j);
            }
        }
    }
}

//输出大端格式的数字
void char_printf_big(char* c, int len)
{
    for(int i=0; i= i; j--, i++)
    {
        char tempnumber = number[j];
        number[j] = number[i] - '0';
        number[i] = tempnumber - '0';
    }
    
    char originalyushu[MAXBIT];
    memset(originalyushu,0,MAXBIT);
    memcpy(originalyushu, number, k);
    char yushu[MAXBIT],product[MAXBIT];

    int N=1; //正在计算循环节长度的位数

    //yushu 保存每次计算的结果
    //小端格式
    memcpy(yushu, number, k);  //1次方的结果
    
    //totaltimes = 累计运算了多少次方
    //大端格式
    char totaltimes[MAXBIT];
    memset(totaltimes,0,sizeof(totaltimes));
    totaltimes[MAXBIT-1]=1; //初始1次方
    
    //前一个位数循环节长度
    //大端格式
    char preN_Times[MAXBIT];
    memset(preN_Times,0,sizeof(preN_Times));
    preN_Times[MAXBIT-1]=1; //初始循环节长度位1
    
    //mulv 保存每次计算要乘的数,就是 输入的 number 的 preN_Times 次方的余数
    //小端格式
    char mulv[MAXBIT];
    memcpy(mulv, number, k); //初始化位1次方的余数
    
    int TestTimes = 10; //测试10次,没有相同的就是没有循环节
    while(TestTimes--)
    {
        //使用原始数据相乘,但不保存结果到yushu, 查看下一次方是否出现循环节了
        calculate(yushu, number, product, k);
        //这里用if而不是while的话,在N和N+1的循环长度一样的情况下会出问题
        //while(!memcmp(product, originalyushu, N))
        while(product[N-1]==originalyushu[N-1]) //本质是上个语句,这样效率更高
        {
            if(N==k)
            {
                char_printf_big(totaltimes,MAXBIT);
                return 0;
            }
            
            N++; 
            
            //前一个位数循环节长度
            memcpy(preN_Times, totaltimes, MAXBIT);
            //保存每次计算要乘的数
            memcpy(mulv, yushu, MAXBIT);
            TestTimes = 10; //测试次数重新计算
            
            // N 加完以后,不要马上计算下一组,要继续测试新的N是否相等,
        }

        //进入下一组数据,相当于次方增加preN_Times次.
        calculate(yushu, mulv, product, k);
        memcpy(yushu,product,k);//保存结果到yushu
        add_big2(totaltimes, preN_Times, MAXBIT);
        
    }
    printf("-1");
    return 0;
}