| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
此打表验证了题目所说的不超过2^63是错误的#include<iostream>
#include<string.h>
using namespace std;
#include<stdio.h>
unsigned __int64 c[432][432];
__int64 nu[432][432];
__int64 lim=__int64(1)<<63-1;
int prime[1000];
int isprime[1000];
int k=0;
void initprime()
{
memset(isprime,0,sizeof(isprime));
isprime[0]=1;
isprime[1]=1;
for(int i=2;i<1000;i++)
{
if(isprime[i])continue;
prime[k++]=i;
for(int j=i*i;j<1000;j+=i)
isprime[j]=1;
}
}
void init()
{
c[0][0]=1;
c[1][0]=1;
c[1][1]=1;
nu[0][0]=1;
nu[1][0]=1;
nu[1][1]=1;
int i,j;
for(i=2;i<=431;i++)
{
c[i][0]=1;
c[i][i]=1;
nu[i][0]=1;
nu[i][i]=1;
for(j=1;j<=i/2;j++)
{
if(c[i-1][j-1]>lim||c[i-1][j]>lim||lim-c[i-1][j-1]<c[i-1][j]||lim-c[i-1][j]<c[i-1][j-1]||c[i-1][j-1]==0||c[i-1][j]==0)break;
c[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][i-j]=c[i][j];
unsigned __int64 sum=1;
unsigned __int64 temp=c[i][j];
for(int x=0;temp!=1;x++)
{
int num=1;
int si=1;
__int64 mi=prime[x];
while(temp%mi==0||temp%prime[x]==0)
{
if(temp%prime[x]==0&&temp%mi!=0)
{
mi=prime[x];
si=1;
}
temp/=mi;
mi*=mi;
num=num+si;
si*=2;
}
sum*=num;
}
nu[i][i-j]=nu[i][j]=sum;
}
}
}
int main()
{
int n,m;
initprime();
init();
while(scanf("%d%d",&n,&m)!=EOF)
{
//cout<<c[n][k]<<endl;
//cout<<nu[n][m]<<endl;
printf("%Id\n",nu[n][m]);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator