#include <stdio.h>
#include <stdlib.h>
int main ()
{
int i;
char R;
int r;
while ( (R = getchar()) != EOF )
{
getchar();
//將 R 轉化為數字
if ( '0' <= R && R <= '9')
r = R - '0';
else if ( 'A' <= R && R <= 'Z' )
r = R - 'A' + 10;
else if ( 'a' <= R && R <= 'z' )
r = R - 'a' + 36;
for (i = 2; i <= 62; i++)
{
if ( (i - 1) % r == 0 )
{
printf ("%d\n", i);
break;
}
else
continue;
}
}
//system("pause");
return 0;
}
posted @
2010-08-29 11:41 雪黛依夢 閱讀(352) |
評論 (0) |
編輯 收藏#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 6 //小數的位數（含小數點）
//將字符轉化為數字
unsigned int change (char s[LENGTH], unsigned int s1[LENGTH - 1])
{
int ss[LENGTH - 1]; //ss 放未逆置的整數
memset (ss, 0, sizeof(ss));
int k = 0 ;
for (int i = 0; i < LENGTH && s[i]; ++i) //考慮特殊數據如：0.0001
{
if (s[i] != '.')
ss[k++] = s[i] - '0';
}
for (int j = 0;j < LENGTH - 1; j++)
{
s1[j] = ss[LENGTH - 2 - j];
}
int m = 0;
while ( (s[m] != '.') && s[m] )
++m;
return LENGTH - 1 - m; //小數點位數
}
//大數乘法運算
//函數返回 s2
void mu1 (unsigned int s1[LENGTH - 1],unsigned int s2[130])
{
int ss[130];
memset ( ss, 0, sizeof(ss) );
for ( int i = 0; i < LENGTH - 1; i++)
for (int j = 0;j < 130; j++) //難點:因為返回新的s2之后位數會增加 最多時 5* 25 = 125
ss [i + j] += s1[i] * s2[j];
//將 兩個大數相乘得的積ss中進行進位處理后放到s2 中
int c = 0;
for (int i = 0;i < 130;i++)
{
s2[i] = (c + ss[i]) % 10;
c = (c + ss[i]) / 10;
}
}
int main()
{
int n;
char s[LENGTH]; //要處理的冪 R
unsigned int s1[LENGTH - 1]; //將 R 轉化成數字
unsigned int s2[130];
while(scanf ("%s%d", s, &n) != EOF)
{
memset (s1, 0, sizeof (s1));
memset (s2, 0, sizeof (s2));
int j = change (s, s1); //得到小數點所在位置
change (s,s2); //得到s2 和 s1 進行冪運算
for ( int i = 1; i < n; i ++)
mu1 (s1,s2);
//在s2中前面的代表小數位，后面的代表整數位，
//所以關鍵是通過數值關系找到小數點的位置
//例：0.1010 * 0.1010 = 0.01020100
int m = 129;//去掉前導0
while ( (!s2[m]) && m)
--m;
int k = 0; //去掉尾0
while ( ( !s2[k] ) && (k < 130))
++k;
//輸出整數位
for (int i = m; i >= n * j; i--)
printf ("%d",s2[i]);
//輸出小數點
if ( j && n * j >= k + 1)
printf (".");
for (int i = n*j -1; i >= k; --i)
printf ("%d", s2[i]);
printf ("\n");
}
return 0;
// system ("pause");
}
posted @
2010-08-29 11:35 雪黛依夢 閱讀(1913) |
評論 (0) |
編輯 收藏#include <stdio.h>
#include <stdlib.h>
#define Tp 23
#define Te 28
#define Ti 33
int main ()
{
int p, e, i, d;
int num = 1;
while (scanf ("%d%d%d%d", &p, &e, &i, &d) != EOF && (p != -1 && e != -1 && i != -1 && d != -1))
{
int j;
for ( j = 1; j <= 21252; j ++)
{
if ( ((j - p) % Tp == 0) && ((j - e) % Te == 0) && ((j - i) % Ti ==0) )
{
if ( j - d > 0)
printf ("Case %d: the next triple peak occurs in %d days.\n", num, j - d);
else
printf ("Case %d: the next triple peak occurs in %d days.\n", num, j - d + 21252);
break;
}
}
num ++;
}
system ("pause");
return 0;
}
http://tiandiwuyong1989.blog.163.com/blog/static/122572981200962121733/本題就是要求得滿足下面條件的 x 的值：
( x - p ) % Tp = 0; ( x - e ) % Te = 0; ( x - i ) % Ti = 0;
由同余可得：x % Tp = p % Tp = a
x % Te = p % Te = b
x % Ti = p % Ti = c
再由中國剩余定理就可以知道了！
//2.用中國剩余定理解
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int p, e, i , d, x;
int Tp = 23, Te = 28, Ti = 33;
int num = 1;
while (scanf ("%d%d%d%d", &p, &e, &i, &d ) != EOF && (p != -1 && e != -1 && i != -1 && d != -1) )
{
int a = p % Tp;
int b = e % Te;
int c = i % Ti;
int n1, n2, n3;
for (int j = 1; j < 33; j ++)
{
if ( (23 * 28 * j) % 33 == 1)
{
n1 = j;
break;
}
}
for (int j = 1; j < 28; j ++)
{
if ( (23 * 33 * j) % 28 == 1)
{
n2 = j;
break;
}
}
for (int j = 1; j < 23; j ++)
{
if ( (33 * 28 * j) % 23 == 1)
{
n3 = j;
break;
}
}
x = (28 * 23 * n1 * c + 23 * 33 * n2 * b + 28 * 33 * n3 * a ) % (23 * 33 * 28);
if ( x - d > 0)
printf ("Case %d: the next triple peak occurs in %d days.\n", num, x - d);
else
printf ("Case %d: the next triple peak occurs in %d days.\n", num, x - d + 21252);
num++;
}
//system ("pause");
return 0;
}
posted @
2010-08-29 11:10 雪黛依夢 閱讀(437) |
評論 (0) |
編輯 收藏
1、先計算Gcd(a,b)，若n不能被Gcd(a,b)整除，則方程無整數解；否則，在方程兩邊同時除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此時Gcd(a',b')=1;
2、利用上面所說的歐幾里德算法求出方程a' * x + b' * y = 1的一組整數解x0,y0，則n' * x0,n' * y0是方程a' * x + b' * y = n'的一組整數解；
3、根據數論中的相關定理，可得方程a' * x + b' * y = n'的所有整數解為：
x = n' * x0 + b' * t
y = n' * y0 - a' * t (t為整數)
上面的解也就是a * x + b * y = n 的全部整數解。
此時方程的所有解為：x=c*k1-b*t。
x的最小的可能值是0
§令x=0，可求出當x最小時的t的取值，但由于x=0是可能的最小取值，實際上可能x根本取不到0，那么由計算機的取整除法可知：由 t=c*k1/b算出的t，代回x=c*k1-b*t中。 §求出的x可能會小于0，此時令t=t+1，求出的x必大于0；如果代回后x仍是大于等于0的，那么不需要再做修正。
//滿足關系：(x + m * s) - (y + n *s) = k*l (k= 0 1 2
)即：(n - m)*s + l*k = x-y;
//利用拓展的歐幾里得解出可能的s
#include <stdio.h>
#include <stdlib.h>
//求最大公約數
__int64 gcd (__int64 a, __int64 b)
{
if (b == 0)
return a;
else
gcd (b, a % b);
}
//求得滿足 a*x + b*y = d；的x y
__int64 ex_Gcd (__int64 a, __int64 b, __int64 &x1, __int64 &y1)
{
if ( b == 0 )
{
x1 = 1;
y1= 0;
return a;
}
int r = ex_Gcd( b, a%b, x1, y1);
int temp = x1;
x1 = y1;
y1 = temp - a/b * y1;
}
int main ()
{
__int64 x, y, m, n, l;
int a, b, product, d;//a b 的最大公約數 product
int s, k;
__int64 s1, k1, s2, k2;
while ( scanf ("%I64d%I64d%I64d%I64d%I64d", &x, &y, &m, &n, &l ) != EOF )
{
a = n - m;
b = l;
d = x-y;
product = gcd (a,b);
if ( d % product != 0 )
printf ("Impossible\n");
else
{
a = a / product;
b = b / product;
d = d / product;
ex_Gcd (a, b, s1, k1); //得到(n-m)/product * s + l/product * k = 1;的 s k的解
s2 = d * s1; //得到(n-m)/product * s + l/product * k = d;的 s k的解
k2 = d * k1;
int t;
//s = s2 - b * t; 用下面的方法處理滿足條件的解
//k = k2 - a * t;
t = s2 / b;
s = s2 - b * t;
if ( s <= 0)
{
s += b;
}
printf ("%d\n", s);
}
}
//system ("pause");
return 0 ;
}
posted @
2010-08-28 22:46 雪黛依夢 閱讀(668) |
評論 (0) |
編輯 收藏講解拓展的歐幾里德算法：
一、內容：
對于不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然存在整數對 x，y ，使得 gcd（a，b）=ax+by。如果gcd(a, b)＝d，那么一定存在x，y滿足ax＋by＝d；
二、推導: 如何求 x y
設 a>b。
1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
2，ab<>0 時
設 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根據樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);
則:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據恒等定理得：x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
三、算法如下：
int exGcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int r = exGcd(b, a % b, x, y);
int temp = x; // x 即 返回的x2
x = y; // x 即要求的 x1
y = temp - a / b * y;
} 理解遞歸 例：a = 48，b = 22 得到 x = 11， y = -24
posted @
2010-08-28 22:05 雪黛依夢 閱讀(322) |
評論 (0) |
編輯 收藏posted @
2010-08-28 21:58 雪黛依夢 閱讀(379) |
評論 (0) |
編輯 收藏
/**//*1.樸素法 只適合 N 很小的時候 復雜度：n * sprt(n)
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int N;
scanf ("%d", &N);
int j,i ;
for ( i = 2; i <= N; i ++) //i
{
for ( j = 2; j*j <= i; j++ )// j <= 根號i
{
if ( i % j == 0 )
break;
}
if ( j*j > i )
printf ("%d ",i);
}
system("pause");
return 0;
}*/
/**//*2.最簡單的素數衰選法:思路：因為偶數不可能是素數，而且第一個奇數是素數，
//故定義一個prime數組，將其下標為偶的初始化為flase，而下表為奇的初始化true，并且奇數的偶數倍false
//輸出 0-100內的素數
//缺點： 奇數的倍數賦為false 時，出現了同一個多次標記；如：3 5 的倍數 15 被兩次標記
#include <stdio.h>
#include <stdlib.h>
int main ()
{
bool prime[101];
int i, j, k;
for ( i = 0; i < 101; i++)
{
if ( i % 2== 0)
prime[i] = false;
else
prime[i] = true;
}
prime[2] = true;prime[1] = false;//特例處理
for ( j = 3; j < 101; j++)//將奇數的倍數賦為false
{
if ( prime[j] == true )
{
for (int m = 2*j; m < 101; m+=j)
{
prime[m] = false;
}
}
}
for ( k = 0; k < 101; k ++)
{
if (prime[k]==true)
printf ("%d ", k);
}
system("pause");
return 0;
}*/
/**//*3.Eraosthenes篩法:得到一個新的素數后將它的倍數剔除掉
//缺點：剔除素數的倍數時，出現了同一個多次標記：如 2 3 的倍數 6 12
#include <stdio.h>
#include <stdlib.h>
int main ()
{
static int prime[101];
prime[0] = 1; prime[1] = 1;
int i , j;
for ( i = 2; i < 101; i ++)
{
if ( ! prime[i] ) //是素數
{
for (j = 2*i; j < 101; j+=i)
{
prime[j] = 1;
}
}
}
for (int m = 2; m < 101; m++)
{
if ( !prime[m] )
printf ("%d ",m);
}
system("pause");
return 0;
}*/
//線性Eraosthenes篩選素數的方法：同樣的思路避免了上述的缺點
//理解這種機制
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000
int tag[MAXSIZE + 1];
int main ()
{
int prime[MAXSIZE];
int i, j;
int cn = 0;
for (i = 2; i< MAXSIZE + 1; i ++)
{
if ( !tag[i] )
prime[cn++] = i;
for ( j = 0; (j < cn) && (prime[j] * i < MAXSIZE + 1) ; j++ )
{
tag[ i * prime[j] ] = 1; //最多標記到本身的倍數，而prime【j】的最大恰好為 i ，而 最大時 j = cn；
if ( i % prime[j] == 0 )
break;
}
}
printf ("%d\n", cn);
for (int m = 0; m < cn; m ++)
{
printf ("%d ",prime[m]);
}
printf ("\n");
system("pause");
return 0;
}
posted @
2010-08-28 21:32 雪黛依夢 閱讀(433) |
評論 (0) |
編輯 收藏
//把任意長度的輸入，通過散列算法，變換成固定長度的輸出
// 經典的哈希算法 這個題目在減少復雜度的方面真的有很多的技巧值得我學習
// 因為直接存儲四項的值 有四重循環，這樣耗時很多，所以開一個滿足題意要求的數組存儲
//等式兩邊的計算值如果出現下標相等就說明滿足題意，同時起到了計數的作用
//因為平方的作用從 1 -- 100 循環減少了復雜度 ，只是記得最后一定要乘以一個16哦！
#include <iostream>
#include <string>
using namespace std;
int hash[2000010];
int main ()
{
int a, b, c, d;
while ( scanf ("%d %d %d %d", &a, &b, &c, &d ) != EOF )
{
if ( ( a > 0 && b > 0 && c > 0 && d > 0 ) || ( a < 0 && b < 0 && c < 0 && d < 0 ))
{
printf ("0\n");
continue;
}
memset ( hash, 0, sizeof (hash) );
int count = 0;
for ( int i = 1; i <= 100; i ++ )
{
for ( int j = 1; j <= 100; j ++ )
{
hash[ a * i * i + b * j * j + 1000000 ] ++; //每一個不同的a*x1^2 + b*x2^2 hash值都是 1
}
}
for ( int i = 1; i <= 100; i ++ )
{
for ( int j = 1; j <= 100; j ++ )
{
count += hash[ 1000000 - c * i * i - d * j * j ]; //如果出現了相同的hash值 則：+ 1
}
}
printf ("%d\n", 16 * count); //反之count會 = 0
}
//system ("pause");
return 0;
}
posted @
2010-08-28 21:16 雪黛依夢 閱讀(472) |
評論 (0) |
編輯 收藏
用 hash 做
| Accepted |
1280 |
0MS |
292K |
1236B |
G++ |
//典型的hash: 用數組下標表示兩兩相加所得到的和，開辟一個滿足題意的大小的數組 sum，
//這樣下標由大到小輸出m個就可以
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int a[3001];
int sum[10001];
int n, m;
while ( scanf ("%d %d", &n, &m) != EOF )
{
memset ( a, 0, sizeof (a) );
memset ( sum, 0, sizeof (sum) );
for ( int i = 0; i < n; i ++ )
{
scanf ("%d", &a[i]);
}
int temp;
for ( int i = 0; i < n; i ++ )
{
for ( int j = i + 1; j < n; j++ )
{
temp = a[i] + a[j];
sum[temp] ++;
}
}
int count = 0; //輸出前 m 個數
for ( int i = 10001; i >= 0 ; i -- )
{
if ( sum[i] )
{
for (int j = 0; j < sum[i]; j ++)
{
count ++;
count == 1 ? printf ("%d", i) : printf (" %d", i);
if ( count == m )
break;
}
}
if ( count == m )
break;
}
printf ("\n");
}
// system ("pause");
return 0;
}
所以改用sort排序后再輸出
| Accepted |
1280 |
843MS |
17888K |
1304B |
G++ |
//典型的hash: 用數組下標表示兩兩相加所得到的和，開辟一個滿足題意的大小的數組 sum，
//這樣下標由大到小輸出m個就可以
#include <iostream>
#include <string>
using namespace std;
int sum[4500000]; //開全局數組才能過
bool cmp ( const int &a, const int &b )
{
return a > b;
}
int main ()
{
int a[3001];
int n, m;
while ( scanf ("%d %d", &n, &m) != EOF )
{
memset ( a, 0, sizeof (a) );
memset ( sum, 0, sizeof (sum) );
//輸入處理
for ( int i = 0; i < n; i ++ )
{
scanf ("%d", &a[i]);
}
//兩數求和
//int k = n * ( n - 1 ) / 2;
int temp = 0;
for ( int i = 0; i < n; i ++ )
{
for ( int j = i + 1; j < n; j ++ )
{
sum[temp ++] = a[i] + a[j];
}
}
sort ( sum, sum + temp, cmp );
int count = 0;
for ( int i = 0; i< temp; i ++ )
{
count ++;
count == 1 ? printf ("%d", sum[i]): printf (" %d",sum[i]);
if ( count == m )
break;
}
printf ("\n");
}
// system ("pause");
return 0;
}
posted @
2010-08-28 16:43 雪黛依夢 閱讀(447) |
評論 (0) |
編輯 收藏//這個題目如果理解了除法的機制就簡單，對于這種 1 / n 的除法因為每次都是用模的10倍去除以除數，
//所以如果出現了模相同必將意味著出現循環節，所以這里用一個標記數組來跳出循環
//這里很容易忽略負數，同時特殊的數 1 的處理
//忘了把最開始的temp = 1 標記為 true 所以WA 了
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int t, n;
int mark[100001];
int res[100001];
while ( scanf ("%d", &t ) != EOF )
{
for ( int i = 0; i < t; i ++ )
{
scanf ( "%d", &n );
if ( n < 0 )
{
printf ("-");
n = -n;
}
if ( n == 1 )
{
printf ("1\n ");
continue;
}
memset ( mark, false, sizeof (mark) );
memset ( res, false, sizeof (mark) );
int temp = 1; //最先的模是 1
mark [ temp ] = true;
int cnt = 0;
while ( temp )
{
temp *= 10;
res[cnt ++] = temp / n;
temp %= n;
if ( mark[temp] )
break;
mark[temp] = true;
}
printf ("0.");
for ( int i = 0; i < cnt; i ++ )
{
printf ("%d", res[i]);
}
printf ("\n");
}
}
// system ("pause");
return 0;
}
posted @
2010-08-28 15:10 雪黛依夢 閱讀(481) |
評論 (0) |
編輯 收藏