首页 > 代码库 > Basic remains

Basic remains

2024-07-17 23:12:07   225人阅读

Problem Description
Given a base b and two non-negative base b integers p and m, compute p mod m and print the result as a base b integer. p mod m is defined as the smallest non-negative integer k such that p = a*m + k for some integer a.
 

Input
Input consists of a number of cases. Each case is represented by a line containing three unsigned integers. The first, b, is a decimal number between 2 and 10. The second, p, contains up to 1000 digits between 0 and b-1. The third, m, contains up to 9 digits between 0 and b-1. The last case is followed by a line containing 0.
 

Output
For each test case, print a line giving p mod m as a base-b integer.
 

Sample Input
2 1100 101
10 123456789123456789123456789 1000
0
 

Sample Output
10
789
 

#include<iostream>
#include <cstring>
#include <stdlib.h>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
int low(int a,int b)
{
    int s=1,r=1;
    while(b!=0)
    {
        if(b&1)
           r*=a;
       a=a*a;
       b>>=1;
    }
    return r;
}
__int64 zhuanhuan(__int64 a,int b)
{
    __int64 sum=0,i=1;
   // cout<<a<<"---"<<endl;
    while(a)
    {
        sum+=(a%10)*i;
        a=a/10;
        i*=b;
    }
    return sum;
}
__int64 er(__int64 a,int b)
{
    __int64 m=0,i=0;
    int aa[20]={0};
    if(a==0){printf("0\n");return 0;}
    while(a)
    {
        aa[i++]=a%b;
        a=a/b;
    }
   for(int j=i-1;j>=0;j--)
    printf("%d",aa[j]);
   printf("\n");
   return 0;
}
int main()
{
    int a,m,l;
    char str[10000];
    while(cin>>a)
    {
         if(a==0)break;
        cin>>str>>m;
        __int64 sm=0,cm=1;
        __int64 sb=zhuanhuan(m,a);
        l=strlen(str);
        {
            for(int i=l-1;i>=0;i--)
            {
                sm=(sm+(str[i]-'0')*cm)%sb;
                cm=(cm*a)%sb;
            }
        }
        __int64 cb=sm%sb;
        er(cb,a);
    }
    return 0;
}




联系
我们