Notepad

NC229015. Notepad

描述

牛牛被所有非传统的事物所吸引。他不再喜欢十进制数制，他决定研究其他数制。一个以 $\ b$ 为基数的数字系统（即b进制数）引起了他的注意。在他开始学习之前，他想在他的记事本中写下这个数字系统中长度为 $\ n$ 的所有数字，但不带前导零。牛牛的记事本中的每一页都有足够的空间来准确地容纳 $\ c$ 个数字。牛牛只写一次每个合适的数字，从第一个空白页开始，不留空白。牛牛从不写前导0，因为他对零除法有不愉快的回忆。

你能帮牛牛找出最后一页上要写多少个数字吗？

输入描述

第一行包括3个正整数。
数字不包含前导零。

输出描述

在唯一的一行输出与最后一个数字写在同一页上的数字数量。

示例1

输入:

2 3 3

输出:

说明:

二进制数系统中正好有 4 个长度为 3 的数字。牛牛在第一页上写了 3 个数字，在第二页上写了 1 个数字。

示例2

输入:

2 3 4

输出:

说明:

二进制数系统中正好有 4 个长度为 3 的数字。所有 4 个数字都可以写在第一页上。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 63ms, 内存消耗: 4208K, 提交时间: 2021-10-27 16:46:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MAXN=1e9+5;
ll c,phi;
string s1,s2;
ll b,n;
ll euler(ll n){
	ll ans=1;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			ans*=i-1;
			n/=i;
			while(n%i==0){
				ans*=i;
				n/=i;
			}
		}
	}
	if(n!=1){
		ans*=n-1;
	}
	return ans;
}
ll get(string s,ll mod){
	ll ans=0;
	for(int i=0;i<s.size();i++){
		ans=ans*10+s[i]-'0';
		ans%=mod;
	}
	return ans;
}
ll qmi(ll a,ll n){
	ll ans=1;
	while(n){
		if(n&1)ans=(ans*a)%c;
		a=(a*a)%c;
		n>>=1;
	}
	return ans;
}
int main(){
	cin>>s1>>s2>>c;
	phi=euler(c);
	b=get(s1,c)%c;
	n=get(s2,phi);
	ll ans=qmi(b,(n-1+phi)%phi)%c*((b-1+c)%c)%c;
	printf("%lld\n",ans==0?c:ans);
	return 0;
}