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

大家帮忙看看,我的code哪里错了

Posted by morenan at 2010-10-18 00:57:33 on Problem 1091
#include<iostream>
#include<stdio.h>
#define MAXN 10000
#define MAXM 100000
#define LIM 10000
#define INF 0x3f3f3f3f
#define FOR(i,l,r) for (i=l;i<=r;i++)
using namespace std;
int i,j,k,l,m,n,ans,cl=0;
static int q[MAXM],c[MAXN],s[MAXN],o[MAXN],b[100];
const int lg[]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
struct high {
       int l,a[100];
       high(int ti=0):l(1) {
           memset(a,0,sizeof(a));a[1]=ti;
           for (;a[l]>=LIM;l++) {
               a[l+1]+=a[l]/LIM;a[l]%=LIM;
           }    
       }
       void demo() {
            for (int i=1;i<=l;i++) printf("%d ",a[i]);
            printf("\n");
       }
       void operator += (high ot) {
            l=max(l,ot.l);
            for (int i=1;i<=l;i++) 
                if ((a[i]+=ot.a[i])>=LIM) {
                   a[i]-=LIM;a[i+1]++;
                }
            for (;a[l+1];l++);
       }
       void operator -= (high ot) {
            l=max(l,ot.l);
            for (int i=1;i<=l;i++) 
                if ((a[i]-=ot.a[i])<0) {
                   a[i+1]--;a[i]+=LIM;
                }
            for (;(l-1) && !a[l];l--);
       }
       void operator *= (high ot) {
            l+=ot.l-1;int i,j;
            memset(b,0,sizeof(b));
            FOR(i,1,l) FOR(j,1,ot.l) 
               if ((b[i+j-1]+=a[i]*ot.a[j])>=LIM) {
                  b[i+j]+=b[i+j-1]/LIM;
                  b[i+j-1]%=LIM;
               }
            for (l=100;!b[l];l--);
            FOR(i,1,l) a[i]=b[i];
       }
       bool operator ! () {
            return (l==1 && !a[1]);
       }
       void output() {
            int i,j,k;
            printf("%d",a[l]);
            for (i=l-1;i;i--) printf("%04d",a[i]);
            printf("\n");
       }
};

void init() {
     int i,j,k;
     FOR(i,2,MAXM-1) if (!q[i]) 
        for (c[++cl]=i,j=2,k=(MAXM-1)/i;j<=k;j++) q[i*j]=1;
     for (j=0,i=1;i<=cl;i++) if (!(m%c[i])) c[++j]=c[i];cl=j;
}

high quick_power(int ti,int nu) {
     high ans(1),dot(ti);
     for (int i=1;lg[i]<=nu;i++) {
         if (nu&lg[i]) ans*=dot;
         dot*=dot;
     }
     return ans;
} 
         
high fin(int u) {
     int i,j,k,top=1,nu=1,max;s[top]=1;
     high ans;
     FOR(i,1,u) nu*=c[i];
     if (u>cl) max=cl; else
        for (max=u;max<cl && nu<=m;nu=(nu*c[max+1])/c[max-u+1],max++);
     for (nu=1;top;) {
           if (top>u) {ans+=quick_power(m/nu,n);i=max+1;}
              else FOR(i,s[top],max) if (nu*c[i]<=m) {
                   nu*=c[i];s[top]=i+1;s[++top]=i+1;o[top]=i+1;
                   break;
                   }
           if (i>max) if (--top) nu/=c[o[top+1]-1];
     }
     return ans;
}
int main() {
    scanf("%d%d",&n,&m);init();
    high ans=quick_power(m,n),dot;
    FOR(i,1,INF) if (!(dot=fin(i))) break; 
       else switch (i&1) {
            case 0:ans+=dot;break;
            case 1:ans-=dot;break;
       }
    ans.output();
    return 1;
}
     

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