求余运算
给出S和M，求0*S%M，1*S%M，2*(M-1)*S%M能否组成一个集合包含
0.1.。。。M-1；（这个是原题意改造而来）；
其实暴力完全可以解决这个问题（⊙﹏⊙b），只是其中用数学方法更加高效，巧妙；
证明如果S和M互质则满足题意：
另G=gcd(S,M);则S=A*G，M=B*G；
另X=K*S%M=K*S-T*M（T为整数，满足X属于0到M-1）；
X=K*A*G-T*B*G;因此取余后的整数一定是G的倍数，G只能取1才能满足条件； 充分性的证明：（即当S与M互质，则0到M-1的S倍对M取余一定能遍历0到M-1）
只需证明的是，该余数中两两之间互不相等；
假设k*S和b*S对M取余相等（k和b∈[0,M)，并且k和b不等);
则k*S=q1*M+r=q2*M+r=b*S <==> （k-b)*S=M*(q1-q2);
S与M互质，由上式子可得M|（k-b），与k和b∈[0,M)，并且k和b不等矛盾；
因此得证；
另外，偶然看到一个很牛叉的辗转相除法；
int gcd(int a,int b)
{
while(b) b^=a^=b^=a%=b;
return a;
}
远程会诊
此代码，很好很强大；把涉及位运算的交换的程序加入，便到得这段简洁高效的代码；
注：A和B；经过A^=B^=A^=B，结果就得到A和B的交换
//////////////////////////// 1000
#include <stdio.h>
int main()
{
int a,b,i,;
scanf("%d",&a);
for(i=1;i<=a;i++)
{ int sum=0;
sum=sum+i;
printf("%d\n",sum);
}
return 0;
};
1001;
#include"stdio.h"
int main()
{
unsigned _int64 n;
unsigned _int64 temp;
while(scanf("%I64u",&n)!=EOF) //是i 非L
{
temp=(1+n)*n/2;
printf("%I64u\n\n",temp);
}
return 0;
}
//////////////////
HDU ACM 1014 Uniform Generator 三月 22nd, acm.hdu.edu/showproblem.php?pid=1014寿命预测
这个题目是判断给定的步长和mod，判断所产生的随机数已经覆盖0~mod-1中所有的数，如果是，则说明所选的步长和mod是一个Good choice，否则为bad choice. 需要懂得的基本内容为线性同余产生随机数，链接：/zh-cn/%E7%B7%9A%E6%80%A7%E5%90%8C%E9%A4%98%E6%96%B9%E6%B3%95
Problem Description
Computer simulations often require random numbers. One way to generate pseudo-random numbers is via a function of the form
seed(x+1) = [seed(x) + STEP] % MOD
where '%' is the modulus operator.
Such a function will generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this effect, selecting the STEP and MOD values caref农业统计分析
ully can result in a uniform distribution of all values between (and including) 0 and MOD-1.
For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of the numbers between and including 0 and MOD-1 will be generated every MOD iterations of the function. Note that by the nature of the function to generate the same seed(x+1) every time seed(x) occurs means that if a function will generate all the numbers between 0 and MOD-1, it will generate pseudo-random numbers uniformly with every MOD iterations.
If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and MOD-1.
Your program will determine if choices of STEP and MOD will generate a uniform distribution of pseudo-random numbers.
Input
Each line of input will contain a pair of integers for STEP and MOD in that order (1 <= STEP, MOD <= 100000).
Output
For each line of input, your program should print the STEP value right- justified in columns 1 through 10, the MOD value right-justified in columns 11 through 20 and either "Good Choice" or "Bad Choice" left-justified starting in column 25. The "Good Choice" message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message "Bad Choice". After each output test set, your program should print exactly one blank line.
Sample Input
3 5
15 20
63923 99999
Sample Output
3 5 Good Choice
15 20 Bad Choice
63923 99999 Good Choice
线性同余方法（LCG）是个产生伪随机数的方法。
它是根据递归公式：
其中A,B,M是产生器设定的常数。
LCG的周期最大为M，但大部分情况都会少于M。要令LCG达到最大周期，应符合以下条件：
B,M互质；
M的所有质因子的积能整除A ? 1；
plmn若M是4的倍数，A ? 1也是；
A,B,N0都比M小；
A,B是正整数。
由以上可知，本题的求解方案。代码如下：
协议分析仪#include <stdio.h>
int main()
{
int a, b, max, min, tmp;
while (scanf("%d%d",&a,&b) != EOF)
{
max = a>b?a:b;
min = a<b?a:b;
while (min)
{
tmp = max%min;
max = min;
min = tmp;折点加氯法去除氨氮
}
if (max==1) printf("%10d%10d Good Choice\n\n", a, b);
else printf("%10d%10d Bad Choice\n\n", a, b);
}
return 0;
/
//////////////////
Problem Description
"OK, you are not too bad, em... But you can never pass the next test." feng5166 says.
"I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers." feng5166 says.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议