#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 雪黛依梦 阅读(325) |
评论 (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 雪黛依梦 阅读(1887) |
评论 (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 雪黛依梦 阅读(420) |
评论 (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 雪黛依梦 阅读(640) |
评论 (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 雪黛依梦 阅读(294) |
评论 (0) |
编辑 收藏posted @
2010-08-28 21:58 雪黛依梦 阅读(361) |
评论 (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 雪黛依梦 阅读(415) |
评论 (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 雪黛依梦 阅读(452) |
评论 (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 雪黛依梦 阅读(425) |
评论 (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 雪黛依梦 阅读(456) |
评论 (0) |
编辑 收藏