posts - 100,  comments - 15,  trackbacks - 0
  2010年10月5日
/*
 * poj1423.cpp
 *  
 *  Created on: 2010-10-5
 *      Author: wyiu
 
*/

#include 
<cstdio>
#include 
<cstring>
#include 
<cmath>
using namespace std;

const double PI = 3.1415926535897932384626433832795;

const double E = 2.71828182845904523536;

int main()
{
    
int m, n;
    
double t;
    
int result;

    scanf(
"%d"&m);

    
while(m--)
    {
        scanf(
"%d"&n);

        t 
= 0.5*log10(2.0*PI*n)+n*log10(n/E);
        result 
= (int)t;
        result
++;
        printf(
"%d\n", result);
        fflush(stdout);
    }
    
return 0;
}
posted @ 2010-10-05 17:08 wyiu 阅读(220) | 评论 (0)编辑 收藏
/*
 * hit1214.cpp
 *  
 *  Created on: 2010-10-3
 *      Author: wyiu
 
*/
#include 
<iostream>
#include 
<string>
#include 
<cstdio>
#include 
<cstring>
using namespace std;

unsigned f[]
={112358132134,
        
5589144233377610987159725844181,
        
67651094617711286574636875025121393196418317811514229,
        
83204013462692178309352457857028879227465,14930352,24157817,39088169,63245986,
        
102334155165580141267914296433494437,701408733113490317018363119032971215073
};

bool check(string s)
{
    
for(int i=0; i<s.length()-1; i++)
        
if(s[i]=='1' && s[i+1]=='1')
            
return false;
    
return true;
}
int main()
{
    
int n;
    unsigned val;
    
int len;
    
string s;
    
int i;

    scanf(
"%d"&n);

    
while(n--)
    {
        cin
>>s;

        val 
= 0;
        len 
= s.length();
        
for(i=len-1; i>=0--i)
        {
            
if(s[i] == '1')
            val 
+= f[len-i];
        }
        printf(
"%u in decimal, ", val);
        fflush(stdout);

        
if(check(s))
        {
            printf(
"already in standard form\n");
            fflush(stdout);
            
continue;
        }

        
for(i=0; i<len && s[i]=='0'; i++);
        
string stds(s.substr(i, len-i));

        
bool changed;
        
while(!check(stds))
        {
            
for(i=0, changed=false; i<stds.length()-1; i++)
            {
                
if(stds[i]=='1' && stds[i+1]=='1')
                {
                    stds[i]
='0';
                    stds[i
+1]='0';
                    
if(i==0)
                        stds 
= string("1")+stds;
                    
else stds[i-1]='1';
                    changed 
= true;
                }
                
if(changed)
                    
break;
            }
        }

        cout
<<"whose standard form is "<<stds<<endl;

    }
    
return 0;
}
posted @ 2010-10-05 15:13 wyiu 阅读(161) | 评论 (0)编辑 收藏
  2010年10月4日
/*
 * 5_9_Strategy.cpp
 *  
 *  Created on: 2010-9-25
 *      Author: wyiu
 
*/

class Compositor
{
public:
    
virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    
int componentCount, int lineWidth, int breaks) = 0;

protected:
    Compositor();

};

//------------------------------------------------------------------------
class Composition
{
public:
    Composition(Compositor 
*);
    
void repair();

private:
    Compositor 
*_compositor;
    Component 
*_components;
    
int _componentCount;
    
int _lineWidth;
    
int *_lineBreaks;
    
int _lineCount;
};

void Composition::repair()
{
    Coord 
*natural;
    Coord 
*stretchability;
    Coord 
*shrinkability;
    
int componentCount;
    
int *breaks;

    
//prepare the arrays with the desired component sizes
    
//

    
//determine where the breaks are:
    int breakCount;
    breakCount 
= _compositor->compose(natural, stretchability, shrinkability,
                                        componentCount, _lineWidth, breaks);

    
//lay out components according to breaks
    
//
}

//--------------------------------------------------------------------
//subclass of Compositor
class SimpleCompositor : public Compositor
{
public:
    SimpleCompositor();

    
virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    
int componentCount, int lineWidth, int breaks);

    
//
};

class TeXCompositor : public Compositor
{
public:
    TeXCompositor();

    
virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    
int componentCount, int lineWidth, int breaks);

    
//
};

class ArrayCompositor : public Compositor
{
public:
    ArrayCompositor();

    
virtual int compose(Coord natural[], Coord stretch[], Coord shrink[],
                    
int componentCount, int lineWidth, int breaks);

    
//
};

//-----------------------------------------
//using example
int main()
{
    
//

    Composition 
*quick = new Composition(new SimpleCompositor);
    Composition 
*slick = new Composition(new TeXCompositor);
    Composition 
*iconic = new Composition(new ArrayCompositor);

    
//.

    
return 0;
}
posted @ 2010-10-04 12:27 wyiu 阅读(121) | 评论 (0)编辑 收藏
  2010年10月3日
F0=0F1=1F2=1F3=2F4=3
F5=5F6=8F7=13F8=21F9=34
F10=55F11=89F12=144F13=233F14=377
F15=610F16=987F17=1,597F18=2,584F19=4,181
F20=6,765F21=10,946F22=17,711F23=28,657F24=46,368
F25=75,025F26=121,393F27=196,418F28=317,811F29=514,229
F30=832,040F31=1,346,269F32=2,178,309F33=3,524,578F34=5,702,887
F35=9,227,465F36=14,930,352F37=24,157,817F38=39,088,169F39=63,245,986
F40=102,334,155F41=165,580,141F42=267,914,296F43=433,494,437F44=701,408,733
F45=1,134,903,170F46=1,836,311,903F47=2,971,215,073F48=4,807,526,976F49=7,778,742,049
int f[47]={0112358132134,
        
5589144233377610987159725844181,
        
67651094617711286574636875025121393196418317811514229,
        
83204013462692178309352457857028879227465,14930352,24157817,39088169,63245986,
        
102334155165580141267914296433494437,70140873311349031701836311903
};
posted @ 2010-10-03 18:13 wyiu 阅读(215) | 评论 (0)编辑 收藏
/*
 * 1250.cpp
 *  
 *  Created on: 2010-10-3
 *      Author: wyiu
 
*/

#include 
<cstdio>
#include 
<cstring>
using namespace std;

int n;
int f[5][2100];

void init()
{
    memset(f, 
0sizeof(f));
    f[
0][0= 1;
    f[
1][0= 1;
    f[
2][0= 1;
    f[
3][0= 1;
    n
--;
}

int fib()
{
    
if(n < 4return 1;

    
int i, j, r, t, m;
    
for(i=4, m=1; i<=n; i++)
    {
        
for(j=0, r=0; j<m; j++)
        {
            t 
= f[(i-1)%5][j]+f[(i-2)%5][j]+f[(i-3)%5][j]+f[(i-4)%5][j] + r;
            f[i
%5][j] = t % 10;
            r 
= t / 10;
        }
        
if(r > 0)
        {
            f[i
%5][j] = r;
            m
++;
        }
    }
    
return m;
}

void display(int m)
{
    
int j;
    
for(j=m-1; j>=0; j--)
    {
        printf(
"%d", f[n%5][j]);
    }
    printf(
"\n");
    fflush(stdout);
}

int main()
{
    
while(scanf("%d"&n) != EOF)
    {
        init();
        
int m = fib();
        display(m);
    }
    
return 0;
}
posted @ 2010-10-03 17:40 wyiu 阅读(309) | 评论 (0)编辑 收藏
/*
 * 1568.cpp
 *  
 *  Created on: 2010-10-2
 *      Author: wyiu
 
*/
#include 
<cstdio>
#include 
<cmath>
using namespace std;

int main()
{

    
int f[30];
    f[
0]=0;
    f[
1]=1;
    
for(int i=2; i<=20; i++)
    {
        f[i] 
= f[i-1+ f[i-2];
    }

    
int n;
    
while(scanf("%d"&n) != EOF)
    {
        
if(n <= 20)
        {
            printf(
"%d\n", f[n]);
            fflush(stdout);
            
continue;
        }
        
double a = -0.5*log10(5+ n*(log10(0.5*(1+sqrt(5.0))));
        
double r = a - int(a);
        
double b = pow(10, r);
        
while(b < 1000)
        {
            b
*=10;
        }
        printf(
"%d\n"int(b));
        fflush(stdout);
    }
    
return 0;
}
posted @ 2010-10-03 16:42 wyiu 阅读(265) | 评论 (0)编辑 收藏
/*
 * 3070.cpp
 *  
 *  Created on: 2010-10-2
 *      Author: wyiu
 
*/
#include 
<cstdio>
using namespace std;
struct Matrix
{
    
int a11, a12;
    
int a21, a22;
};

Matrix mutilMatrix(Matrix a, Matrix b)
{
    Matrix c;
    c.a11 
= (a.a11*b.a11+a.a12*b.a21 ) % 10000;
    c.a12 
= (a.a11*b.a12+a.a12*b.a22 ) % 10000;
    c.a21 
= (a.a21*b.a11+a.a22*b.a21 ) % 10000;
    c.a22 
= (a.a21*b.a12+a.a22*b.a22 ) % 10000;
    
return c;

}

Matrix powerMatrix(
int n)
{
    
if(n == 0)
    {
        Matrix m0 ;
        m0.a11
=1;
        m0.a12
=0;
        m0.a21
=0;
        m0.a22
=1;
        
return  m0;
    }
    
else
    {
        Matrix a, b;
        a 
= powerMatrix(n/2);
        b 
= mutilMatrix(a, a);
        
if(n%2 != 0)
        {
            Matrix m1 ;
            m1.a11
=1;
            m1.a12
=1;
            m1.a21
=1;
            m1.a22
=0;

            b 
= mutilMatrix(b, m1);
        }
        
return b;
    }

}

int main()
{
    
int n;
    
while(scanf("%d"&n) != EOF)
    {
        
if(n == -1)
            
break;

        Matrix r 
= powerMatrix(n);

        printf(
"%d\n", r.a12);
        fflush(stdout);
    }
    
return 0;
}
posted @ 2010-10-03 16:41 wyiu 阅读(152) | 评论 (0)编辑 收藏
  2010年10月2日
/*
 * 1021.cpp
 *  
 *  Created on: 2010-10-2
 *      Author: wyiu
 
*/

#include 
<cstdio>
#include 
<cstring>
using namespace std;

int f[1000001];

int main()
{
    f[
0]=7%3;
    f[
1]=11%3;
    
for(int i=2; i<=1000000; i++)
    {
        f[i] 
= (f[i-1+ f[i-2]) % 3;
    }

    
int x;
    
while(scanf("%d"&x) != EOF)
    {
        
if(f[x] == 0)
            printf(
"yes\n");
        
else printf("no\n");
        fflush(stdout);
    }
    
return 0;
}
posted @ 2010-10-02 16:48 wyiu 阅读(157) | 评论 (0)编辑 收藏
  2010年3月31日
//推出同余式后直接上算法导论结论
#include <iostream>
using namespace std;
__int64 extgcd(__int64 a, __int64 b, __int64 
&x, __int64 &y)
{
    
if(b==0)
    
{
        x
=1,y=0;return a;
    }

    __int64 r
=extgcd(b,a%b,x,y);
    __int64 t
=x; x=y; y=t-a/b*y;
    
return r;
}

int main()
{
    __int64 x,y,m,n,l,k,t;
    __int64 a,b,c,d;
    
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&n,&m,&l)!=EOF)
    
{

        a
=m-n;
        b
=x-y;
        
if(m-n<0)
        
{
            a
=-a;
            b
=(-b+l)%l;
        }

        
else b=(b+l)%l;
        d
=extgcd(a,l,k,t);
        
if(b%d) { printf("Impossible\n"); continue;}
        k
=(k*(b/d)%l+l)%(l/d);

        printf(
"%I64d\n", k);
    }

    
return 0;
}


posted @ 2010-03-31 22:54 wyiu 阅读(544) | 评论 (0)编辑 收藏

A+C*X=B(%2^K)
C*X=B-A(%2^K)
令a=c,b=B-A,n=2^K;
 利用以下结论(具体证明见《算法导论):
推论1:方程ax=b(mod n)对于未知量x有解,当且仅当gcd(a,n) | b。
推论2:方程ax=b(mod n)或者对模n有d个不同的解,其中d=gcd(a,n),或者无解。
定理1:设d=gcd(a,n),假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b,则方程ax=b(mod n)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n,方程ax=b(mod n)的最小整数解x1=e mod (n/d),最大整数解x2=x1+(d-1)*(n/d)。
定理2:假设方程ax=b(mod n)有解,且x0是方程的任意一个解,则该方程对模n恰有d个不同的解(d=gcd(a,n)),分别为:xi=x0+i*(n/d) mod n 。

a*x=b(%n) => a*x+n*y=b
d=ext_gcd(a,n,x0,y0)
最小整数解x1=(x0*(b/d)%n+n)%(n/d);
  

#include <iostream>
using namespace std;
__int64 exgcd(__int64 a, __int64 b, __int64 
&x, __int64 &y)
{
    
if(b==0)
    
{
        x
=1;y=0;return a;
    }

    __int64 r
=exgcd(b, a%b, x, y);
    __int64 t
=x;x=y;y=t-a/b*y;
    
return r;
}

int main()
{
    __int64 A,B,C,K;
    __int64 a,b,n,d,x,y,e;
    
while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&K)!=EOF)
    
{
        
if(A==0 && B==0 && C==0 && K==0break;
        a
=C;
        n
=((__int64)1<<K); //小心溢出
        b=B-A;
        d
=exgcd(a, n, x, y);
        
if(b%d) {printf("FOREVER\n"); continue;}
        e
=x*(b/d)%n+n;
        printf(
"%I64d\n",e%(n/d));
    }

    
return 0;
}
;
posted @ 2010-03-31 22:48 wyiu 阅读(154) | 评论 (0)编辑 收藏
仅列出标题  下一页