就是求各种进制下求mod;

m没有超给过long int 的界限,所以可以直接装换成long int 行

但是p很大。

我的方法是把每一位提出来求mod,

比如输入为2 11001  1000

变成(1*2^4modm+1*2^3modm+1modm)mod m

代码:

 

#include <iostream>
#include <math.h>
using namespace std;
__int64 mod(__int64 a,__int64 b)
{
return (a%b+b)%b;
}
__int64 ctoi(char *a,int bb)
{
    __int64 ans=0;
 int s=strlen(a);
 for(int i=0;i<s;i++)
 {
  ans+=int(a[i]-48)*pow(float(bb),s-i-1);
 }
 return ans;
}
void itoa(__int64 ans,char *a,int bb)
{
 char c[11];
 int i=0,j=0;
 while(ans)
 {
  c[i++]=char(ans%bb+48);
  ans/=bb;
 }
 for(j=0;j<i;j++)
 {
  a[j]=c[i-j-1];
 }
 return ;
}
__int64 onemod(__int64 num,int d,int bb,__int64 m)
{
 __int64 ans=bb;
 if(d>=1)
 {
 while(d>1)
 {
  if(d%2==0)
  {
   d/=2;
   ans=mod(ans*ans,m);
  }
  else
  {
   d–;
   num=mod(num*ans,m);
  }
 }
 return ans=mod(num*ans,m);
 }
 else
 {
  return ans=mod(num,m);
 }
}
__int64 mod1(char *p,__int64 m,int bb)
{
 __int64 ans=0;
 int s=strlen(p);
 for(int i=0;i<s;i++)
 ans+=onemod(int(p[i]-48),s-i-1,bb,m);
 return mod(ans,m);
}
int main()
{
 char p[1010];
 char m[12];
 char ans[12];
 int b;

 while(cin>>b&&b)
 {
  __int64 tans;
  __int64 mm;
  memset(ans,0,sizeof(ans));
  memset(p,0,sizeof(p));
  memset(m,0,sizeof(m));
  cin>>p>>m;
        mm=ctoi(m,b);
  tans=mod1(p,mm,b);
  itoa(tans,ans,b);
  if(ans[0]!=0)
  cout<<ans<<endl;
  else
   cout<<“0″<<endl;
 }
 return 0;
}

相关文章