首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CodeForces 17D Notepad(同余定理)

CodeForces 17D Notepad(同余定理)

作者头像
ShenduCC
发布2018-04-26 16:01:56
4450
发布2018-04-26 16:01:56
举报
文章被收录于专栏:算法修养算法修养

D. Notepad

time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

Nick is attracted by everything unconventional. He doesn't like decimal number system any more, and he decided to study other number systems. A number system with base b caught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of length n without leading zeros in this number system. Each page in Nick's notepad has enough space for c numbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number 0 as he has unpleasant memories about zero divide.

Would you help Nick find out how many numbers will be written on the last page.

Input

The only input line contains three space-separated integers bn and c (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). You may consider that Nick has infinite patience, endless amount of paper and representations of digits as characters. The numbers doesn't contain leading zeros.

Output

In the only line output the amount of numbers written on the same page as the last number.

Examples

input

2 3 3

output

1

input

2 3 4

output

4

题目的意思就是求 ((b-1)* b ^(n-1))%c

如果用java高精度加快速幂来求,肯定会爆炸,因为有一百万位。

这道题目完全可以不用快速幂,利用同余定理就可以了,当然用了快速幂会更快一些

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <queue>

using namespace std;
#define MAX 1000000
char b[MAX+5];
char n[MAX+5];
long long int c;
int main()
{
    while(scanf("%s%s%lld",b,n,&c)!=EOF)
    {


    long long int num=0;//b
    long long int num2=0;//b-1
    int len=strlen(b);
    //b
    for(int i=0;i<len;i++)
        num=(b[i]-'0'+num*10)%c;
    //b-1
    for(int i=len-1;i>=0;i--)
      if(b[i]!='0'){b[i]--;break;}
      else  b[i]='9';
    for(int i=0;i<len;i++)
        num2=(b[i]-'0'+num2*10)%c;
        
    int len2=strlen(n);
    long long int ans=0;
    long long int num3=num;
    //n-1
    for(int i=len2-1;i>=0;i--)
      if(n[i]!='0'){n[i]--;break;}
      else  n[i]='9';
     
    for(int j=0;j<len2;j++)
    {
        if(n[j]!='0')
        {
            if(j!=0)
            {
                 long long int num4=num;
                 for(int k=1;k<=9;k++)
                     num=((num%c)*num4)%c;
            }
            int x=n[j]-'0';
            if(j==0)
                x--;
            for(int p=1;p<=x;p++)
              num=((num%c)*num3)%c;
        }
        else
        {
            if(j!=0)
            {
                long long int num4=num;
                for(int k=1;k<=9;k++)
                    num=((num%c)*num4)%c;
            }
            else
               num=1;
        }
    }
    num=((num%c)*(num2%c))%c;
    if(num==0)
        num=c;
    printf("%lld\n",num);
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-04-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档