Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 提供高精度对拍。。

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;
}
}
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: