- 浏览: 308206 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
http://poj.org/problem?id=1006&lang=zh-CN&change=true
Sample Input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
Sample Output
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
中国剩余定理【孙子定理】详解:
其实就是解方程组:
求res的值
使用中国剩余定理的条件【重要!!!】:
n1,n2,n3……ni 这些数两两互质(互素)!!也就是两两之间的最大公约数是1!!
回到正题:先看一下这个视频,后面的会更好理解!
http://v.youku.com/v_show/id_XMTExNTAzOTIw.html
算法描述:【利用同余的加性和乘性】
令nn = n1×n2×n3×……×ni;
那么也就是说nn是ni的倍数!
所以有:nn/ni是其他n的倍数,不是ni的倍数,而且nn/ni跟ni没有大于1的公约数
【如nn/n2,是n1,n3,n4...的倍数,但不是n2的倍数,而且nn/n2和n2的最大公约数是1,因为上面说了这些数两两互质】
既然nn/ni是其他n的倍数,那么nn/ni这个数模其他n【n1,n2...n[i-1],n[i+1]...】的结果肯定是0,为下面利用同余的加性奠定了基础
所以根据视频那种方法
可以先找到x使得:
假设找到这个x了,那么要满足第i个方程,则利用同余的乘性必有:
那么就是res的一部分,它使得res满足第i个方程
所以利用同余的加性,把满足所有方程的这么一个部分加起来就是求出来的其中一组解了
怎么找x呢?【关键】
∵有重要条件:两两互质
∴nn/ni和ni也互质
∴【根据上述:使用中国剩余定理的条件】
∴由扩展的【欧几里得】得:
∴两边同时模ni得:
跟上面的式子对比,发现x = x0
x0怎么求?
不就是利用【扩展欧几里得定理】咯!
另外推荐题目:http://acm.hdu.edu.cn/showproblem.php?pid=1930
Sample Input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
Sample Output
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
中国剩余定理【孙子定理】详解:
其实就是解方程组:
求res的值
使用中国剩余定理的条件【重要!!!】:
n1,n2,n3……ni 这些数两两互质(互素)!!也就是两两之间的最大公约数是1!!
回到正题:先看一下这个视频,后面的会更好理解!
http://v.youku.com/v_show/id_XMTExNTAzOTIw.html
算法描述:【利用同余的加性和乘性】
令nn = n1×n2×n3×……×ni;
那么也就是说nn是ni的倍数!
所以有:nn/ni是其他n的倍数,不是ni的倍数,而且nn/ni跟ni没有大于1的公约数
【如nn/n2,是n1,n3,n4...的倍数,但不是n2的倍数,而且nn/n2和n2的最大公约数是1,因为上面说了这些数两两互质】
既然nn/ni是其他n的倍数,那么nn/ni这个数模其他n【n1,n2...n[i-1],n[i+1]...】的结果肯定是0,为下面利用同余的加性奠定了基础
所以根据视频那种方法
可以先找到x使得:
假设找到这个x了,那么要满足第i个方程,则利用同余的乘性必有:
那么就是res的一部分,它使得res满足第i个方程
所以利用同余的加性,把满足所有方程的这么一个部分加起来就是求出来的其中一组解了
怎么找x呢?【关键】
∵有重要条件:两两互质
∴nn/ni和ni也互质
∴【根据上述:使用中国剩余定理的条件】
∴由扩展的【欧几里得】得:
∴两边同时模ni得:
跟上面的式子对比,发现x = x0
x0怎么求?
不就是利用【扩展欧几里得定理】咯!
另外推荐题目:http://acm.hdu.edu.cn/showproblem.php?pid=1930
#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <set> //#include <map> #include <queue> #include <utility> #include <iomanip> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <ctype.h> using namespace std; void Egcd (int a, int b, int &x, int &y) //扩展欧几里得【无返回版】求x { if (b == 0) { x = 1, y = 0; return ; } Egcd (b, a%b, x, y); int tp = x; x = y; y = tp - a/b*y; } int CRT (int n[], int b[], int nn) { int res = 0, x, y, i; for (i = 0; i < 3; i++) { int a = nn / n[i]; Egcd (a, n[i], x, y); //求x res += a * x * b[i]; //把所有组成部分加起来【加性】 } //其中*b[i]是利用了同余的乘性 return res; } int main() { int n[5] = {23, 28, 33}, b[5], i, date, k = 1, x0; while (1) { for (i = 0; i < 3; i++) scanf ("%d", b+i); scanf ("%d", &date); if (date == -1) break; x0 = (CRT (n, b, 21252) - date) % 21252; //使解不大于21252 if (x0 <= 0) x0 += 21252; //负数或0特殊考虑 printf ("Case %d: the next triple peak occurs in %d days.\n", k++, x0); } return 0; }
发表评论
-
HDU 4746 Mophues
2013-10-01 17:29 2974莫比乌斯函数完整定义的通俗表达: 1)莫比乌斯函数μ(n ... -
HDU 3221 Brute-force Algorithm
2013-05-04 13:31 1656/* * [题意] * 略 * [解题方法] ... -
UVA 10168 Summation of Four Primes
2013-02-14 21:48 1778/* * [题意] * 将一个数拆成四个素数的和, ... -
UVA 10139 Factovisors
2013-02-09 22:56 2108/* * [题意] * 判断n!是否能被m整除(n ... -
UVA 10104 Euclid Problem
2013-02-09 22:50 1473新手请进:扩展欧几里德入门 /* * ... -
UVA 10006 Carmichael Numbers
2013-02-08 08:27 2420/* * [题意] * 输入n,若满足如下两个条件 ... -
UVA 10110 Light, more light
2013-02-08 08:23 1399/* * [题意本质] * 输入n,如果n的约 ... -
【polya+Euler】HDU 2239 机器人的项链
2012-08-20 13:06 1414KIDx的解题报告 题目 ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1073KIDx的解题报告 题目链接:http://ac ... -
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2622KIDx的解题报告 题 ... -
【扩展欧几里德】SGU 106
2012-05-22 23:57 2279KIDx的解题报告 题目链接:http://acm.s ... -
【数论+容斥】POJ 1091 跳蚤
2012-05-17 13:11 3243KIDx的解题报告 题目链接:http://poj.o ... -
【数论法求一堆数的最小公倍数,结果高达几千位】LOJ 1024 Eid
2012-02-10 16:22 1778KIDx的解题报告 题意:求n个数的最小公倍数,结果很大 ... -
【预处理+卡特兰数+乘法逆元+二分查找】LOJ 1170
2012-01-14 12:57 2222KIDx 的解题报告 题目链接:http://ligh ... -
【快速幂取模】fzu 1752 A^B mod C
2011-11-25 23:32 3636KIDx 的解题报告 参考《算法艺术与信息学竞赛》: 题目 ... -
【高次幂取模的应用】HDU 3609 Up-up
2011-11-25 22:42 2248KIDx 的解题报告 题目很容易看懂:http://acm.h ... -
模线性方程组-非互质中国剩余定理 (更新于2012/5/18)
2011-11-18 19:03 4632KIDx 的解题报告 该专题必备知识:解模线性方程 http: ... -
【素数筛法小结】fzu 1607 + fzu 1753
2011-11-16 23:06 1665KIDx 的解题报告 http://acm.fzu.edu.c ... -
HDU 1410 PK武林盟主
2011-10-02 16:28 1096KIDx 的解题报告 题目链接: http://acm.h ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2544KIDx 的解题报告 http://acm.hdu.ed ...
相关推荐
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
北大POJ1006-Biorhythms【中国剩余定理】 解题报告+AC代码
人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度...
解决poj1006问题
北大POJ1129-Channel Allocation【四色定理】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1001答案