Skip to content

Instantly share code, notes, and snippets.

@yuikns
Last active December 16, 2015 13:29
Show Gist options
  • Save yuikns/5441855 to your computer and use it in GitHub Desktop.
Save yuikns/5441855 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <string.h>
#define LEN 110
using namespace std;
char s[200]; // 输入串
int k; // 输入参数
int result[LEN] ; // 存放结果
void M2AA(int a[], int b[], int b1, int c[],int c1)
// 被乘数a,可有c1位,乘数b有b1位(b1可以为1,或大于1),积c有c1位。
{
int i,j;
for(i=0;i<c1;i++) c[i]=0;
if (b1 > c1) b1 = c1; // 取乘数的有效位
for(i=0; i<b1; i++) // 乘数
{ if (b[i])
{
for(j=0; j<c1-i; j++) // 被乘数
{
c[i+j] = a[j]*b[i] + c[i+j];
c[i+j+1]= c[i+j+1] + c[j+i]/10;
c[i+j] = c[i+j]%10;
}
}
}
}
int main()
{
int a[LEN],b[LEN],c[LEN],aa[LEN];
int i,j,tp,num,n;
std::cin>>s>>k;
n=strlen(s);
for(i=0;i<n;i++)
a[n-i-1] = s[i] - '0'; // 将字符转换为数字保存在a数组中。
for (i=0; i<k; i++) aa[i] = a[i]; // 将原数保存在aa中
result[0]=1;
for(i=0; i<k; i++)
{
for(j=0;j<=i;j++) b[j]=aa[j];
tp=b[i];
num=0;
do
{
M2AA(a, b, i+1, c, i+1);
num++;
for(n=0; n<k; n++) b[n]=c[n];
} while ((num<10) && (b[i]!=tp));
if(b[i]!=tp)
{
std::cout<<-1<<endl;
return 0;
}
for(j=0;j<k;j++)
b[j] = a[j];
for(j=0;j<num-1;j++) // 求a=a^num
{
M2AA(a, b, k, c, k);
for(n=0;n<LEN;n++)
a[n]=c[n];
}
M2AA(result, &num,1, c, LEN);
for(n=0; n<LEN; n++)
result[n]=c[n];
}
for (i=LEN-1; result[i]==0; i--);
for( ; i>=0 ; i--)
std::cout<<result[i];
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment