/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 3ms 360.0 KiB
#2 Accepted 4ms 336.0 KiB
#3 Wrong Answer 3ms 356.0 KiB
#4 Runtime Error 5ms 360.0 KiB
#5 Runtime Error 3ms 356.0 KiB
#6 Runtime Error 5ms 356.0 KiB
#7 Runtime Error 4ms 384.0 KiB
#8 Runtime Error 3ms 360.0 KiB
#9 Runtime Error 5ms 344.0 KiB
#10 Runtime Error 5ms 372.0 KiB

代码

#include<bits/stdc++.h>
#define LL long long
int d=0;
LL a,n,k,ans=1,prime[100];;
inline const void get_prime()
{
	bool pp;
	for(LL i=2;i<=a;i++)
	{
		pp=true;
		for(LL j=1;j<=d;j++)
		{
			if(!(i%prime[j]))
			{
				pp=false;
				break;
			}
		}
		if(pp)prime[++d]=i;
	}
}
inline const LL fast_pow(LL x,LL y)
{
	LL base=x,ans=1,r=y;
	while(r)
	{
		if(r&1)ans=ans*base%k;
		r=r>>1;base=base*base%k;
	}
	return ans;
}
inline const LL gcd(LL x,LL y)
{
	if(y==0)return x;
	return gcd(y,x%y);
}
inline const LL lcm(LL x,LL y)
{
	if(x<y)return lcm(y,x);
	return x/gcd(x,y)*y;
}
LL factor[100];
int tot=0;
inline const void resolve()
{
	for(int i=1;i<=d;i++)
	{
		if(a==1)break;
		while(!(a%prime[i]))
		{
			a/=prime[i];
			factor[++tot]=prime[i];
		}
	}
}
int main()
{
	std::cin>>a>>n>>k;
	get_prime();
	resolve();
	LL ans=1;
	for(LL i=1;i<=(1<<tot)-1;i++)
	{	
		LL c=0,om=1;
		for(LL j=1;j<=tot;j++)
		{
			if(i&(1<<(j-1)))
			{	
				om*=factor[j];
				c^=1;
			}
		}
		if(c)ans=ans*fast_pow(om,n/om)%k;
		else ans=ans*fast_pow(fast_pow(om,n/om),k-2)%k;
	}
	std::cout<<ans;
	return 0;
}

信息

递交者
类型
递交
题目
学前班数学(原创)
题目数据
下载
语言
C++
递交时间
2017-10-13 20:05:38
评测时间
2017-10-13 20:05:38
评测机
分数
20
总耗时
45ms
峰值内存
384.0 KiB