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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

提供高精度对拍。。

Posted by wzc1995 at 2013-02-06 22:16:03 on Problem 1091
INPUT
15 99999998
OUTPUT
999969182430861644191190369959924944476815948692873202450224989685661666093474545006276876118091153296424483844374122632

INPUT
15 99999999
OUTPUT
999999780308301338108398984878799086845371774472580917862145195630829005720627227908349397537382053091743102906934400000

INPUT
15 100000000
OUTPUT
999969482389108000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int prime[100],cnt;
struct H
{int a[200],len;}ans,res;
inline H operator * (const H &x,const H &y)
{
	H z;
	memset(&z,0,sizeof z);
	for(int i=1;i<=x.len;i++)
		for(int j=1;j<=y.len;j++)
		{
			z.a[i+j-1]+=x.a[i]*y.a[j];
			z.a[i+j]+=z.a[i+j-1]/10;
			z.a[i+j-1]%=10;
		}
	if(z.a[x.len+y.len]) z.len=x.len+y.len;
	else z.len=x.len+y.len-1;
	return z;
}
inline H power(int x,int y)
{
	H tot,p;
	memset(&tot,0,sizeof tot);
	memset(&p,0,sizeof p);
	tot.len=1;tot.a[1]=1;
	while(x)
	{
		p.a[++p.len]=x%10;
		x/=10;
	}
	while(y)
	{
		if(y&1) tot=tot*p;
		p=p*p;y>>=1;
	}
	return tot;
}
inline H operator + (const H &x,const H &y)
{
	H z;
	memset(&z,0,sizeof z);
	z.len=max(x.len,y.len);
	for(int i=1;i<=z.len;i++)
	{
		z.a[i]+=x.a[i]+y.a[i];
		z.a[i+1]+=z.a[i]/10;
		z.a[i]%=10;
	}
	if(z.a[z.len+1]) z.len++;
	return z;
}
inline H operator - (const H &x,const H &y)
{
	H z;
	memset(&z,0,sizeof z);
	z.len=max(x.len,y.len);
	for(int i=1;i<=z.len;i++)
	{
		z.a[i]+=x.a[i]-y.a[i];
		if(z.a[i]<0) z.a[i+1]--,z.a[i]+=10;
	}
	while(!z.a[z.len]&&z.len>1) z.len--;
	return z;
}
inline void dfs(int deep,int x,int now,int tot)
{
	if(x==tot)
	{
		res=res+power(m/now,n);
		return;
	}
	if(deep==cnt+1) return;
	dfs(deep+1,x,now,tot);
	dfs(deep+1,x+1,now*prime[deep],tot);
}
inline void print(const H &x)
{
	for(int i=x.len;i;i--) printf("%d",x.a[i]);
	printf("\n");
}
int main()
{
	scanf("%d%d",&n,&m);
	ans=power(m,n);
	int t=m;
	for(int i=2;i*i<=t;i++)
	{
		if(t%i==0) prime[++cnt]=i;
		while(t%i==0) t/=i;
	}
	if(t>1) prime[++cnt]=t;
	for(int i=1;i<=cnt;i++)
	{
		memset(&res,0,sizeof res);
		dfs(1,0,1,i);
		if(i&1) ans=ans-res;
		else ans=ans+res;
	}
	print(ans);
	return 0;
}

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