Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes!

造 福 人 类

Posted by juruo_zzt at 2020-05-18 20:11:52 on Problem 1845
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e7+10;
const int MOD=9901;
int qpow(int a,int n,int m)
{
	int base=a%m,ans=1;
	while(n)
	{
		if(n&1) ans=(ans*base)%m;
		base=(base*base)%m;
		n>>=1;
	}
	return ans;
}
int a[N],c[N],n,b,cnt=0;
void init()
{
	int i=2;
	while(n>1)
	{
		if(!(n%i))
		{
			n/=i;
			a[++cnt]=i;
			c[cnt]=1;
			while(!(n%i))
			{
				n/=i;
				c[cnt]++;
			}
		}
		i++;
		if(i*i>n) break;
	}
	if(n>1) 
	{
		a[++cnt]=n;
		c[cnt]++;
	}
}
int inv(int s,int p) {return qpow(s,p-2,p);}
int main()
{
	scanf("%d %d",&n,&b);
	init();
	int ans=1;
	for(int i=1;i<=cnt;i++)
	{
		if((a[i]-1)%MOD)
		{ 
			int z=c[i]*b+1;//指数
			int in=inv(a[i]-1,MOD);//inv(a-1)
			int s=(qpow(a[i],z,MOD)-1+MOD)%MOD;
			s=(s*in)%MOD;
			ans=(ans*s)%MOD;
		}
		else ans=ans*(b%MOD*c[i]+1)%MOD;
	}
	printf("%d",ans);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator