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;
}
/*
* hit1214.cpp
*
* Created on: 2010-10-3
* Author: wyiu
*/
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
unsigned f[]={1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,14930352,24157817,39088169,63245986,
102334155, 165580141, 267914296, 433494437,701408733, 1134903170, 1836311903, 2971215073
};
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;
}
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;
}
2010年10月3日
| F0= | 0 | F1= | 1 | F2= | 1 | F3= | 2 | F4= | 3 |
| F5= | 5 | F6= | 8 | F7= | 13 | F8= | 21 | F9= | 34 |
| F10= | 55 | F11= | 89 | F12= | 144 | F13= | 233 | F14= | 377 |
| F15= | 610 | F16= | 987 | F17= | 1,597 | F18= | 2,584 | F19= | 4,181 |
| F20= | 6,765 | F21= | 10,946 | F22= | 17,711 | F23= | 28,657 | F24= | 46,368 |
| F25= | 75,025 | F26= | 121,393 | F27= | 196,418 | F28= | 317,811 | F29= | 514,229 |
| F30= | 832,040 | F31= | 1,346,269 | F32= | 2,178,309 | F33= | 3,524,578 | F34= | 5,702,887 |
| F35= | 9,227,465 | F36= | 14,930,352 | F37= | 24,157,817 | F38= | 39,088,169 | F39= | 63,245,986 |
| F40= | 102,334,155 | F41= | 165,580,141 | F42= | 267,914,296 | F43= | 433,494,437 | F44= | 701,408,733 |
| F45= | 1,134,903,170 | F46= | 1,836,311,903 | F47= | 2,971,215,073 | F48= | 4,807,526,976 | F49= | 7,778,742,049 |
int f[47]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,14930352,24157817,39088169,63245986,
102334155, 165580141, 267914296, 433494437,701408733, 1134903170, 1836311903
};
/*
* 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, 0, sizeof(f));
f[0][0] = 1;
f[1][0] = 1;
f[2][0] = 1;
f[3][0] = 1;
n--;
}
int fib()
{
if(n < 4) return 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;
}
/*
* 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;
}
/*
* 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;
}
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;
}
2010年3月31日
//推出同余式后直接上算法導(dǎo)論結(jié)論
#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;
}
A+C*X=B(%2^K)
C*X=B-A(%2^K)
令a=c,b=B-A,n=2^K;
利用以下結(jié)論（具體證明見《算法導(dǎo)論）：
推論1：方程ax=b(mod n)對(duì)于未知量x有解，當(dāng)且僅當(dāng)gcd(a,n) | b。
推論2：方程ax=b(mod n)或者對(duì)模n有d個(gè)不同的解，其中d=gcd(a,n)，或者無解。
定理1：設(shè)d=gcd(a,n)，假定對(duì)整數(shù)x和y滿足d=ax+by(比如用擴(kuò)展Euclid算法求出的一組解)。如果d | b，則方程ax=b(mod n)有一個(gè)解x0滿足x0=x*(b/d) mod n 。特別的設(shè)e=x0+n，方程ax=b(mod n)的最小整數(shù)解x1=e mod (n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。
定理2：假設(shè)方程ax=b(mod n)有解，且x0是方程的任意一個(gè)解，則該方程對(duì)模n恰有d個(gè)不同的解(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)
最小整數(shù)解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==0) break;
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;
};