#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "math.h"
#include "ctype.h"
#include "string.h"
#define MAX_SIZE 50
void multi(int *a,int *result,int base);
void power(int time,int *result,int base);
void transform(int *result,char *str,int base);
int cal_len(long sum);
int residue(int *result,long sum);
int check(char *str,int base);
int main()
{
int base,flag=0,i,j,sum=0,result[MAX_SIZE*4]={0};
long resi=0;
char str_num[MAX_SIZE];
puts("Enter the base:");
scanf("%d",&base);
fflush(stdin);
puts("Now enter the number:");
do
{
if(flag)
puts("Input Wrongly! Enter again:");
gets(str_num);
}while((flag=check(str_num,base)));
for(i=0;i<strlen(str_num);sum+=str_num[i++]-48);
transform(result,str_num,base);
i=residue(result,(long)sum);
for(j=i;j>=0;j--)
resi+=(long)result[j]*(long)pow(10,j);
resi%(long)sum?puts("Not niven number!"):puts("Yes,it's a niven number!");
system("pause");
}
int residue(int *result,long sum)
{
int i,j,k,flag=0,length=cal_len(sum);
long trans=0;
char str_num[11];/*long型最多2147483647,刚好10位*/
while(1)
{
for(i=MAX_SIZE*4-1;!result[i];i--);
if(i-length<=0)
return i;
for(j=i-length;j<=i;j++)
trans+=(long)result[j]*(long)pow(10,j+length-i);
if(trans<sum)
{
trans=0;
flag=1;
for(j=i-length-1;j<=i;j++)
trans+=(long)result[j]*(long)pow(10,j+length+1-i);
}
trans%=sum;
ltoa(trans,str_num,10);
k=strlen(str_num);
if(flag)
{
for(j=i-length-1;j<=i;j++)
{
k--;
if(k>=0)
result[j]=str_num[k]-48;
else
result[j]=0;
}
}
else
{
for(j=i-length;j<=i;j++)
{
k--;
if(k>=0)
result[j]=str_num[k]-48;
else
result[j]=0;
}
}
trans=0,flag=0;
}
}
int cal_len(long sum)
{
int length=0;
long num=sum/10;
while(num>0)
length++,num/=10;
return length;
}
int check(char *str,int base)
{
int i=0;
while(str[i])
{
if(!isdigit(str[i])) return 1;
if(str[i++]>=base+48) return 1;
}
return 0;
}
void power(int time,int *result,int base)
{
int i=0,a1[MAX_SIZE*4]={0},a2[MAX_SIZE*4]={0};
if(time)
{
a1[0]=base;
while(++i!=time)
{
if(i%2)
multi(a1,a2,base);
else
multi(a2,a1,base);
}
if(time%2)
{
for(i=0;i<MAX_SIZE*4;i++)
result[i]=a1[i];
}
else
{
for(i=0;i<MAX_SIZE*4;i++)
result[i]=a2[i];
}
}
else result[0]=1;
}
void multi(int *a,int *result,int base)
{
int i,j,k;
for(k=MAX_SIZE*4-1;!a[k];k--);
for(i=0;i<MAX_SIZE*4;result[i++]=0);
for(j=0;j<=k;j++)
{
result[j+1]+=result[j]/10;
result[j]%=10;
result[j]+=a[j]*base;
result[j+1]+=result[j]/10;
result[j]%=10;
}
}
void transform(int *result,char *str,int base)
{
int i,j,k=strlen(str);
for(i=0;i<k;i++)
{
int transi1[MAX_SIZE*4]={0},transi2[MAX_SIZE*4]={0};
power(k-i-1,transi1,base);
multi(transi1,transi2,str[i]-48);
for(j=0;j<MAX_SIZE*4-1;j++)
{
result[j]+=transi2[j];
result[j+1]+=result[j]/10;
result[j]%=10;
}
}
}