LOFTER for ipad —— 让兴趣,更有趣

点击下载 关闭

LOFTER-网易轻博

数论

1757浏览    101参与
hdw2000
hdw2000
hdw2000
hdw2000
hdw2000
SyrvaLand

LRQorz!!

修正了(我的瞎jr简化幼儿版)cayley定理证明。

lrqfakedzztqlorzakioi!!!

修正了(我的瞎jr简化幼儿版)cayley定理证明。

lrqfakedzztqlorzakioi!!!

方鸢子
[组合数学|容斥原理] 模板代...

[组合数学|容斥原理]

模板代码(以求2,3,5,7倍数为例)

要点:二进制枚举

vector<int> ans;
ans.push_back(2);
ans.push_back(3);
ans.push_back(5);
ans.push_back(7);
long long  sum=0;
for(int i=1;i<(1<<ans.size());i++)
 {
  int cnt=0;
  long long tmp=1;
  for(int j=0;j<ans.size();j++)
  ...

[组合数学|容斥原理]

模板代码(以求2,3,5,7倍数为例)

要点:二进制枚举

vector<int> ans;
ans.push_back(2);
ans.push_back(3);
ans.push_back(5);
ans.push_back(7);
long long  sum=0;
for(int i=1;i<(1<<ans.size());i++)
 {
  int cnt=0;
  long long tmp=1;
  for(int j=0;j<ans.size();j++)
  {
   if(i&(1<<j))
   {
    tmp=tmp*ans[j];
    cnt++;
   }
  }
  if(cnt&1) sum+=n/tmp;
  else sum-=n/tmp;
 }

方鸢子
[算法|数论]GCD的性质 1...

[算法|数论]GCD的性质

1.等价律

gcd(x,n)=i等价于gcd(x/i,n/i)=1

2.结合律&交换律:

gcd(a1,a2)=gcd(a2,a1)

gcd(a1,a2,...,an)=gcd(a1,gcd(a2,..,an))

3.单调性/收敛性

例如:以4开头往后区间的gcd可能为: 4 4 2 2 2 2 1 1 1 1 1 1

而不可能为: 2 2 4 1 1 1 4 2 2 1 1 1

同具有收敛性的还有&&和||运算等


GCD模板:(a,b大小无影响)

long long gcd(long long a,long long...

[算法|数论]GCD的性质

1.等价律

gcd(x,n)=i等价于gcd(x/i,n/i)=1

2.结合律&交换律:

gcd(a1,a2)=gcd(a2,a1)

gcd(a1,a2,...,an)=gcd(a1,gcd(a2,..,an))

3.单调性/收敛性

例如:以4开头往后区间的gcd可能为: 4 4 2 2 2 2 1 1 1 1 1 1

而不可能为: 2 2 4 1 1 1 4 2 2 1 1 1

同具有收敛性的还有&&和||运算等


GCD模板:(a,b大小无影响)

long long gcd(long long a,long long b)
{
    return b==0?a:gcd(b,a%b);
}

Utopia
hehe0__0
天龙神剑

卡巴拉密教 七艺之数论 (八至十五数)

本文转自:http://blog.sina.com.cn/s/blog_7ba3ce520100vhgw.html

写在前面,Every fact of science was once Damned. 每个科学定理都曾经被咒骂过。Every invention was considered impossible. 每个发明都曾被认为是无稽之谈。Every discovery was a nervous shock to some orthodoxy. 每个新发现都能让原教旨主义或保守主义者精神崩溃。Every artistic innovation was denounced...

本文转自:http://blog.sina.com.cn/s/blog_7ba3ce520100vhgw.html

写在前面,Every fact of science was once Damned. 每个科学定理都曾经被咒骂过。Every invention was considered impossible. 每个发明都曾被认为是无稽之谈。Every discovery was a nervous shock to some orthodoxy. 每个新发现都能让原教旨主义或保守主义者精神崩溃。Every artistic innovation was denounced as fraud and folly. 每个艺术创新都曾被公开指责为山寨货或傻逼玩意。The entire web of culture and "progress," everything on earth that is man-made and not given to us by nature, is the concrete manifestation of some man's refusal to bow to Authority. 整个文化和“进步”网络,地球上每件事物都是人造的并非大自然直接赋予我们的,是一部分人类拒绝向权威屈服“人定胜天”思维的具体表现。We would own no more, know no more, and be no more than the first apelike hominids if it were not for the rebellious, the recalcitrant, and the intransigent.如果没有反叛顽抗和不妥协者,我们现在不会比第一个猿人拥有更多、懂得更多、甚至与猿人不会有什么两样。As Oscar Wilde truly said, "Disobedience was man's Original Virtue."奥斯卡王尔德曾经真诚地告诉世人:“反抗是人类原始的美德。”——以上是BOB罗伯特安东威尔逊说法,当然他同时强调:Trust No One But Yourself...除了你自己不要相信任何人。。。
《卡巴拉密教学校第一堂试听课:卡巴拉密教 七艺之数论》第一课:总论,零至七 我们讲到了卡巴拉之树能量结构的数字量化零至七,我们这节课要继续讲八至十五。。。


第一图,古埃及卡巴拉之树,虽然这个图不做我们这个试听课的教材(稍后也许根据网络解密进程会做同步讲解),但是为了向现代光明会符号——未完工的金字塔上面天道之独眼的符号致敬。编辑Sonychen666决定特别在课前进行一个感性的描述。
这是一个西方流行的概念,采用了古埃及的金字塔与上面隐形的天道之独眼代表尚未完工的宇宙,因罗伯特安东威尔逊的《光明会人三部曲》七十年代的系列小说而成为一种文化现象。随着互联网的普及事情变得狂野而邪门。你们知道吗?最早的世界统一政府的概念是伊扎克牛顿提出来的。因为他发现了这个抽象的概念并且为之而着迷后半生。遗憾的是牛顿没有从理论高度描述出来这个量子物理宇宙观,量子的破粒二象性之后的描述。而这个天道独眼现在有了个学名,叫做,“奇点大爆炸”。。。
奇点,就是奇异点,我们创世的量子世界最早的理想形式,这个点在我们人类神秘的大脑中也有存在,不过那将会是个说来话长的故事了,在此不再继续。有兴趣的读者可以阅读 @摩罗街摩罗客 的《摩罗街2012世界的逆转》中“祥叔”对于量子宇宙即将实现的时空穿梭的体会,“。。。我会选择回到过去。。。”他的这句话恰好就是时空旅行的关键词,回到过去做“自己”的上帝!做“自己”历史的扳道工(紫薇星明的说法)!Do What Thou Wilt!当你经历过了一切,你必将对自己的过去有一个评判,而你大脑中有个叫松果体的地方,那个地方偏偏就可以接收到“天道之独眼”量子奇异点的信号,当所有人都成为自己的主人之后,人类共有的世界才会改变
11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI
第二图,一美元中的各种神秘符号数字的卡巴拉解释,书归正传,上面BlahBlah大段的量子宇宙和金字塔独眼只是作为引子,你们才不会因为兴趣索然而昏昏欲睡。比如猫头鹰,古希腊神话雅典娜的猫头鹰代表“注视,清晰的眼睛”Α?Ε两个圈想不想8倒过来无限的符号?数字8是天秤座,数字16是火星塔罗牌的高塔(8和无限符号的双螺旋),上一课讲过巨蟹座的数字7塔罗牌是战车,它还有个名字叫做梅尔卡巴。两个梅尔卡巴旋转即7+7=14代表天道之独眼(77),有大量的数字13,这是天蝎的数字代表死亡与重生。。。所以一美元的设计者不是阴谋论患者而是炼金术密教中人。
11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

8 数字八


卡巴拉第九个数字,希伯来苔丝,赶牛羊的鞭杖(横着拿)或铁锹铲子,塔罗牌第十一号审判,灵魂的天秤

希腊神话中的天秤座,古埃及地狱判官,天秤永远与死神在一起生于九十月份的黄道十二星座之守护星座天秤座
占星术中的天秤座,公平正义与普世美感,中国十二属相中的狗,也代表忠诚与一分辛劳一分收获,数字是八是中国人的幸运数字,原因是天秤座在黄道中代表秋分是收获的季节。八卦中的艮卦,代表山,幼子。

古埃及阿努比斯(狗头神)在地狱用女神麦特Ma'at的羽毛称重已经死亡的心脏。。。
古希腊神话中天秤座是冥王黑帝斯的金马车,冥王正是乘坐这架马车吧女神抢走强奸的。。。
(注*:这张牌的希伯来字是属于后面狮子座的拉米德,应该是第九个希伯来字苔丝如上)
11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

9 数字九


卡巴拉第十个数字,希伯来耀得,(伸出的)手有时候也做眼睛,塔罗牌的第九号隐者,内省与反思

希腊神话中的处女座(室女座),负责孕育的处女神生于八九月份的黄道十二星座之守护星座处女座
占星术中的处女座,天生担心狂和精神洁癖,中国十二属相中的鸡,也代表谦逊和重分析的知识分子,数字九是中国王权完美数字,原因是这代表下一个轮回的开始。八卦中的离卦,代表中女,喜用红色(公鸡的鸡冠)。希腊神话中女神的总和,黄金时代的统治。共济会名言Ordo Ab Chaos“混乱中孕育秩序”的意思。

11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

10 数字十


卡巴拉第十一个数字,希伯来卡夫,手掌或投掷用的链球,塔罗牌的第十号牌命运之轮,表示命运周而复始的运转

希腊神话中的天神宙斯,木星命运之神
射手和双鱼座的守护神(天神,海神,冥王三位一体)
占星术中的木星,幸运。八卦中重新九九归一。希腊神话的天神宙斯众神之父。
11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

11 数字十一


卡巴拉第十二个数字,希伯来拉米的,蟒蛇或者狮子,塔罗牌的第八号力量,耐心驯服力量

希腊神话中的狮子座,代表勇气力量生于七八月份的黄道十二星座之守护星座狮子座
占星术中的狮子座,代表国王老板,中国十二属相中的猴。炼金术中炼金方法,炼金最后阶段。数字十一是神秘学中的大师数字,第一个即单数初始数1又1+1=2是第一个偶数初始数。螺旋状态的希腊完结字母欧米伽OMEGA=Ω
圣经联系狮子羔羊,羔羊是圣经卷开始Α,狮子是圣经卷结束Ω,这是圣经密码中的人类文明的炼金长卷
崇拜狮子羔羊lionlamb,不要拜虚假的偶像,不要计算并且等待虚假的“救世主”的降临人间。。。
古埃及壁画屠蛇勇士
壁画中的屠蛇勇士,勇者斗恶龙的传说。。。
苏美尔遗迹石刻中的狮子和白羊

苏美尔狮子与圣蛇权杖与DNA螺旋的联系
密宗瑜伽的kundalini
炼金术图画一
炼金术图画二

与零能量点永动还有极移的联系


(注*:这张牌的希伯来字是属于前面天秤座的苔丝,应该是第十一个希伯来字拉米的如上)
【四幺八茶道】UBS瑞士银行大门正上方的天使就是狮子座的天使黄金守护神,而钥匙则是圣殿骑士团的标志
【四幺八茶道】这是罗斯柴尔德家在法国的庄园,拉菲古堡酒庄的神像雕塑,不用解释,黄金炼金术的守卫者。
【四幺八茶道】狮子作为财富守护者的传统,不仅仅中国有,埃及有,西藏有希腊西方各国都有类似传统。。。
11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

12 数字十二


卡巴拉第十三个数字,希伯来语麦姆,代表水,塔罗牌的第十二号倒吊男,“以将有更美好的事物降临于你身上的信念,顺从于人生”
代表炼金术四大元素的水元素,炼金术的四大物质状态的湿润

11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

13 数字十三


卡巴拉第十四个数字,希伯来语纳赫,代表一个杯子,塔罗牌的第十三号死神,意味着某种状况的结束和终结。

表示万千变化,“看我七十二变”的死神,也是炼金术中所暗喻的鱼,蝎子,巨蟒和凤凰,十二星座的天蝎座
古埃及的蝎子王拿摩
古埃及传授高深炼金术知识《翠玉集》的透特神

蝎子座还被抽象为蜘蛛和蜘蛛网,下面是美洲印第安预言家霍皮老妈妈的形象
古希腊黄道十二星座传说中神秘的隐藏的第十三星座,希腊神话中的阿拉克尼,吕底亚的科洛丰少女,精于织布,与雅典娜比赛织布,雅典娜将阿拉克尼的织绣毁掉,阿拉克尼想自缢,被雅典娜点化成蜘蛛。。。
三重伟大的赫尔姆斯(赫尔墨斯,爱马仕)手中的蚕丝地球,神圣知识的讲述者
炼金术含义为创造,死亡-重生,地球水晶以及晶体的创造力量
共济会标志时间沙漏和骷髅


11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI


14 数字十四


卡巴拉第十五个数字,希伯来语萨麦赫,代表炼金术的月亮老人,塔罗牌的第十四号节制,光明会之瞳,代表行动及感情的融合。

十二星座射手座的穿透力与精确洞察力,共济会的拱门和支柱

希腊神话中的喀戎或者奇戎,半人马,酒神狄俄倪索斯的随从。
11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI11x8x11ChAI

15 数字十五


卡巴拉第十六个数字,希伯来语阿吟,代表炼金术的双腿,塔罗牌的第十五号魔鬼,代表错以为别无选择。
苏美尔神话中最强大的神祗,古巴比伦叫法易阿,EA,是一个深海之神,与造人神话有关
也是海中长角之神大衮和森林之神潘神
冬至日色坦尼亚
圣殿骑士团的巴佛麦特(巴哈姆特)神


来源:Dionysius

风灵无畏OI

数论专题(我会慢慢补齐)

一 初等整数数论


1.1  取模运算   http://tzdyy.lofter.com/post/1e3cd119_e213ffd

     (这个为本人自己写的博客)

       1.1.1 次幂取模 http://liaoy148.lofter.com/post/1da8a74e_b582025

       1.1.2 相乘取模 http...

一 初等整数数论


1.1  取模运算   http://tzdyy.lofter.com/post/1e3cd119_e213ffd

     (这个为本人自己写的博客)

       1.1.1 次幂取模 http://liaoy148.lofter.com/post/1da8a74e_b582025

       1.1.2 相乘取模 http://liaoy148.lofter.com/post/1da8a74e_b590ff8

     (这两个为liaoy学长的博客,因为懒,所以就没写了QWQ)


1.2 最大公约数和最小公倍数

      最大公约数记作:gcd(a,b)=1,  Greatest Common Divisor

      最小公倍数记作:lcm(a,b),        Least Common Multiple

                         http://tzdyy.lofter.com/post/1e3cd119_e221e4c

      (这个为本人自己写的博客,里面牵扯到了扩展欧几里得算法,后面也会再提)

        对于最小公倍数:lcm(a,b)=a*b/gcd(a,b);


1.3 质数

       http://tzdyy.lofter.com/post/1e3cd119_ee47bb8

    (这个为自己编写)



【特别鸣谢】

    MDZX第一歌姬——wwl学姐(以上的蓝色背景的图片都是这位学姐制作的PPT节选而来)

    MDZX四大金刚之一——liaoy学长(链接了学长的博客,另外感谢学长的辛勤辅导)

    MDZX2016届高一大佬——hjl(大佬的题解)

风灵无畏OI

线性方程组

(以下内容来自百度百科)

线性方程组

      线性方程组是各个方程关于未知量均为一次方程组(例如2元1次方程组)。

一 、简介

    xj表未知量, aij称系数, bi称常数项。

    称为系数矩阵增广矩阵

    若x1=c1,x2=c2,…,xn=cn代入所给方程各式均成立,则称(c1,c2,…,cn)为一个解。

    若c1,c2,…,cn...

(以下内容来自百度百科)

线性方程组

      线性方程组是各个方程关于未知量均为一次方程组(例如2元1次方程组)。

一 、简介

    xj表未知量, aij称系数, bi称常数项。

    称为系数矩阵增广矩阵

    若x1=c1,x2=c2,…,xn=cn代入所给方程各式均成立,则称(c1,c2,…,cn)为一个解。

    若c1,c2,…,cn不全为0,则称(c1,c2,…,cn)为非零解

    若常数项均为0,则称为齐次线性方程组,它总有零解(0,0,…,0)。

    两个方程组,若它们的未知量个数相同解集相等,则称为同解方程组

    线性方程组主要讨论的问题是

    ①一个方程组何时有解。

    ②有解方程组解的个数。

    ③对有解方程组求解,并决定解的结构。

    这几个问题均得到解决:

    所给方程组有解,则秩(A)= 秩(增广矩阵);

    若秩(A)=秩=r,则r=n时,有唯一解;

    r<n时,有无穷多解; 可用消元法求解。

(简介就说到这儿了,如果对线性方程组有更多的兴趣,大家可以去看一下百度百科)


风灵无畏OI

矩阵的秩(不完整版)

(以后会补齐)

线性代数中,一个矩阵A的列秩是A的线性独立的纵列的极大数。

通常表示为r(A),rk(A)或rank A。

http://baike.baidu.com/view/346467.htm


(以后会补齐)

线性代数中,一个矩阵A的列秩是A的线性独立的纵列的极大数。

通常表示为r(A),rk(A)或rank A。

http://baike.baidu.com/view/346467.htm


风灵无畏OI

增广矩阵

   (以下内容来自百度百科)   

       增广矩阵又称(扩增矩阵)就是在系数矩阵的右边添上一列,这一列是线性方程组等号右边的值。

       系数矩阵是矩阵中的众多类型之一,简单来说系数矩阵就是将方程组的系数组成矩阵来计算程的解 。

示例

如:

方程AX=b 系数矩阵为A,它的增广矩阵为(A b)。

增广矩阵通常用于判断矩阵的有解的情况,比如说:

  1. r(...

   (以下内容来自百度百科)   

       增广矩阵又称(扩增矩阵)就是在系数矩阵的右边添上一列,这一列是线性方程组等号右边的值。

       系数矩阵是矩阵中的众多类型之一,简单来说系数矩阵就是将方程组的系数组成矩阵来计算程的解 。

示例

如:

方程AX=b 系数矩阵为A,它的增广矩阵为(A b)。

增广矩阵通常用于判断矩阵的有解的情况,比如说:

  1. r(A)<r(A b) 方程组无解;

  2. r(A)=r(A B)=n,方程组有唯一解;

  3. r(A)=r(A B)<n,方程组无穷解;

  4. r(A)>r(A B)不可能,因为增广矩阵的秩大于等于系数矩阵的秩。

对于方程组(1):

a11 x1+a12 x2+a13 x3+…+a1n xn=b1(1)

a21 x1+a12 x2+a23 x3+…+a2n xn=b2(2)

……………………

ai1 x1+ai2 x2+ai3 x3+ … +ain xn=bi(i)

……………………

am1 x1+am2 x2+am3 x3+…+amn xn=bm(m)

分类

系数矩阵为:

[ a11   a12   a13  …   a1n ]

[ a21   a22   a23  …   a2n ]

[ ……………………............... ]

[ ai 1    a i 2  a i 3  …  a i n ]

[ ……………………............... ]

[ am 1 am 2 am 3… am n ]

增广矩阵为:

[ a11   a12  a13 …  a1n b1 ]

[ a21   a22  a23 …  a2n b2 ]

[ ………………………...............]

[ ai 1    ai 2   ai 3 …  ai n bi   ]

[ ……………………….............. ]

[ am1 am2  am3 … amn bm]

      补充:上面说的只是在解线性方程组的时候,对系数矩阵进行的一个增广矩阵,切勿以为增广矩阵只是右端添加一列,其实是在原矩阵的右端添加一个矩阵,而线性方程组的右端恰好是一个列数为1的矩阵。


风灵无畏OI

高斯消元法(不完整版)

【概念】

(大家也可以先不看这一部分,可以后先跳过这一部分,但本人建议还是先看一下为好)

线性方程组:http://tzdyy.lofter.com/post/1e3cd119_e2bdf1b

增广矩阵:    http://tzdyy.lofter.com/post/1e3cd119_e2bdefc

矩阵的秩:    http://tzdyy.lofter.com/post/1e3cd119_e2bdf0e

友情链接:    http://liaoy148.lofter...

【概念】

(大家也可以先不看这一部分,可以后先跳过这一部分,但本人建议还是先看一下为好)

线性方程组:http://tzdyy.lofter.com/post/1e3cd119_e2bdf1b

增广矩阵:    http://tzdyy.lofter.com/post/1e3cd119_e2bdefc

矩阵的秩:    http://tzdyy.lofter.com/post/1e3cd119_e2bdf0e

友情链接:    http://liaoy148.lofter.com/post/1da8a74e_bab1d62

【高斯消元】

       我们知道解一元一次方程,二元一次方程,一元二次方程甚至三元一次方程,但是更多元或者更高次的方程,我们可能就不会了,或者用脑子搞出来就会很繁琐。而对于四元及以上的多元一次方程便可以用计算机来解决。

       我们首先定义一个增广矩阵,有系数及右边的常数组成。(具体可见上面的链接)

现在假设有这么一个方程组:

        2x + 3y + 11z + 5w = 2

          x +   y +   5z + 2w = 1

        2x +   y +   3z +  2w = -3

          x +   y +   3z +  4w = -3

现在我们把它编一个号:  

        2x + 3y + 11z + 5w = 2   (1)

          x +   y +   5z + 2w = 1   (2)

        2x +   y +   3z +  2w = -3 (3)

          x +   y +   3z +  4w = -3 (4)

我们把它转成一个增广矩阵:

        2      3    11     5     2

        1      1      5     2     1

        2      1      3     2    -3

        1      1      3     4    -3

第一步:我们把第(1)行的都乘以1/2,于是就变成了这样

        1       3/2    11/2    5/2    1

        1         1         5       2      1

        2         1         3       2     -3

        1         1         3       4     -3

               然后再把(1)* -1 + (2)去更新(2)

                          把(1)* -2 +(3)去更新(3)

                          把(1)* -1 +(4) 去更新(4)

于是我们便得到一个新的矩阵:

        1       3/2    11/2    5/2     1

        0      -1/2    -1/2    -1/2     0

        0       -2        -8        -3     -5

        0      -1/2     -5/2    3/2     -4

第二步:我们再把(2)*-2于是就变成了这样

        1       3/2    11/2    5/2     1

        0         1         1        1      0

        0       -2        -8        -3     -5

        0      -1/2     -5/2    3/2     -4

               然后再把(2)*2+(3)去更新(3)

                         把(2)*1/2+(4)去更新(4)

于是我们便得到一个新的矩阵:

        1       3/2    11/2    5/2     1

        0         1         1        1      0

        0         0        -6       -1     -5

        0         0        -2         2    -4

第三步:我们再把(3)*-1/6于是就变成了这样

        1       3/2    11/2    5/2     1

        0         1         1        1      0

        0         0         1      1/6   5/6

        0         0        -2         2    -4

                  然后再把(3)*2+(4)去更新(4)

        1       3/2    11/2    5/2     1

        0         1         1        1      0

        0         0         1      1/6   5/6

        0         0         0      7/3   -7/3

第四步:我们再把(4)*3/7于是就变成这样 

        1       3/2    11/2    5/2     1

        0         1         1        1      0

        0         0         1      1/6   5/6

        0         0         0        1     -1

当然,如果消元消到最后发现a[n,0]<>0而a[n,n]=0,那么证明无解了(一定是无解,否则在之前就已经因为上述理由而结束程序)。而我们要知道这个方程组它是无解还是有无穷解,则可以用上面提到的去看矩阵的秩来判断。

第五步:回代

当我们做完第四部之后,我们便可以解出w了,因为此时的方程(4)可以表示为1*w=-1,于是我们可以得到w=-1,接着方程三便可以表示为1*z+1/6*w=5/6,得到z=1,继续往上做,便可得到y=0,x=-2。

例题链接:https://www.luogu.org/problem/show?pid=3389

 

【程序代码】(由于现在还没写,所以就先把学长的代码给放上来了QWQ)

pascal版:(liaoy大师的,大家可以自行理解一下)

type

func=array[0..1000] of double;//方程

var

a:array[1..1000] of func;//增广矩阵

x:array[1..1000] of double;//解

n,i,j:longint;


function count(i:longint):double;//求x[i]

var

  vi:longint;

  t:double;

begin

  t:=0;

  for vi:=i+1 to n do

   t:=t+x[vi]*a[i,vi];//计算除了当前要求的x以外其他的数之和

  t:=a[i,0]-t;

  x[i]:=t/a[i,i];

  exit(x[i]);

end;


function minus(x,y:func):func;//方程相减

var

  vi:longint;

begin

  fillchar(minus,sizeof(minus),0);

  for vi:=0 to n do

   minus[vi]:=x[vi]-y[vi];

end;


function multiply(x:func;y:double):func;//方程乘上一个数

var

  vi:longint;

begin

  fillchar(multiply,sizeof(multiply),0);

  for vi:=0 to n do

   multiply[vi]:=x[vi]*y;

end;


procedure gaosi(i,j:longint);//一个方程i消i+1到n的一个元

var

  l1,l2:double;

  vi:longint;

  t:func;

begin

  t:=a[i];//之后要把这个玩意还原到原来的数,否则会越来越大更加容易溢出

  l1:=a[i,i];

  l2:=a[j,i];

  a[j]:=multiply(a[j],l1);

  a[i]:=multiply(a[i],l2);

  a[j]:=minus(a[i],a[j]);

  a[i]:=t;

end;


procedure aswap(var a,b:func);//交换方程

var

  c:func;

begin

  c:=a;

  a:=b;

  b:=c;

end;


procedure not0(i:longint);//若当前方程要消的元的系数为0,就找一个去换

var

  vi:longint;

begin

  for vi:=i+1 to n do

   if a[vi,i]<>0 then

   begin

    aswap(a[i],a[vi]);

    exit;

   end;

  writeln('No check answer');//找不到去换

  halt;

end;


begin

read(n);

for i:=1 to n do

begin

  for j:=1 to n do//读入

   read(a[i,j]);

  read(a[i,0]);

end;


for i:=1 to n-1 do//高斯消元

begin

  if a[i,i]=0 then not0(i);//判断是否需要换方程

  for j:=i+1 to n do

   if a[j,i]<>0 then gaosi(i,j);//把i+1到n的方程全部消一个元

end;


if (a[n,0]<>0) and (a[n,n]=0) then//判断是否无解

begin

  writeln('No check answer');

  halt;

end;


for i:=n downto 1 do//计算x

  count(i);


for i:=1 to n do

  writeln('x',i,'=',x[i]:0:6);//输出

end.

风灵无畏OI

欧拉定理与费马小定理(简单版)

博客链接http://liaoy148.lofter.com/post/1da8a74e_b61006b

由于现在还不太会,并且也没提多时间,所以就先链接一位学长的博客,供大家看看。(以后我会再写)


博客链接http://liaoy148.lofter.com/post/1da8a74e_b61006b

由于现在还不太会,并且也没提多时间,所以就先链接一位学长的博客,供大家看看。(以后我会再写)


风灵无畏OI

线性筛

https://www.luogu.org/problem/show?pid=3383

【题目描述】

如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)

【输入格式】

第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数,即询问概数是否为质数。

 【输出格式】 

输出包含M行,每行为Yes或No,即依次为每一个询问的结果。

【输入样例】

100 5

91 

97

【输出样例】

Yes

Yes...

https://www.luogu.org/problem/show?pid=3383

【题目描述】

如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)

【输入格式】

第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数,即询问概数是否为质数。

 【输出格式】 

输出包含M行,每行为Yes或No,即依次为每一个询问的结果。

【输入样例】

100 5

91 

97

【输出样例】

Yes

Yes 

No 

No 

Yes

 【说明】 

时空限制:500ms 128M

数据规模:

对于30%的数据:N<=10000,M<=10000

对于100%的数据:N<=10000000,M<=100000

样例说明:

N=100,说明接下来的询问数均不大于100且大于1。

所以2、3、97为质数,4、91非质数。

故依次输出Yes、Yes、No、No、Yes。

【题目分析】

      此题大家一看到应该就知道,普通的筛法是做不了的,我们只能想想比如线性筛,欧拉线性筛,Miller_Rabin加二次探测什么的(我也不是很懂),于是就用了最简单的线性筛。

【算法讲解】

      这里有一位学长讲线性筛的博客:http://liaoy148.lofter.com/post/1da8a74e_b60a4cc

可以去看看他的,讲的很仔细。

       我就长话短说吧,我们用p[i]记录当前为止第i个素数。f[i]true表示i是合数。从2开始枚举。对于每一个数 i ,如果not f[i],我们就把i扔进p数组。i 就是我们枚举到的这个数字,

i mod p[j]=0的时候我们就弹出这样是不是就保证了, i*p[j]是被它最小的p[j]筛去的

因为一个数字只被最小的质因子筛去只被for一次

所以复杂度是O(n)

【程序代码】

var  n,m,i,x,tot:longint;

     f:array[0..10000010]of boolean;

     p:array[0..10000010]of longint;//数组要开这么大,范围有这么大

procedure prime_table(n:longint);

var i,j:longint;

begin

  tot:=0;

  f[1]:=true;//这里是需要注意的,当时我就是没注意这里,结果一直wa两个点,后面还是经某何大佬,才A的题。

  for i:=2 to n do

   begin

     if f[i]=false then//表示i为质数

       begin inc(tot); p[tot]:=i; end;//把素数按从小到大加入

     j:=1;

     while i*p[j]<=n do//保证查找的数在1~n范围内

      begin

        if j>tot then break;//这里是一个小小的优化,

        f[i*p[j]]:=true;//表示i*p[j]为合数

        if i mod p[j]=0 then break;

        inc(j);

      end;

   end;

end;

begin

  readln(n,m);

  prime_table(n);//线性筛,把1~n中的素数找出来

  for i:=1 to m do

   begin

    readln(x);

    if f[x]=false then writeln('Yes')

    else writeln('No');//输出

   end;

end.











风灵无畏OI

欧几里得算法(未完成版)

以下内容部分来自度娘,另一部分来自百度百科。

http://baike.baidu.com/item/扩展欧几里德算法

【介绍】

       扩展欧几里德算法是用来在已知a, b求解一组x,y,使它们满足贝祖等式: ax+by = gc

d(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程

组中。

【欧几里得算法】

一、概述

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖下面的定理:

gcd函数就是用来求(a,...

以下内容部分来自度娘,另一部分来自百度百科。

http://baike.baidu.com/item/扩展欧几里德算法

【介绍】

       扩展欧几里德算法是用来在已知a, b求解一组x,y,使它们满足贝祖等式: ax+by = gc

d(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程

组中。

【欧几里得算法】

一、概述

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖下面的定理:

gcd函数就是用来求(a,b)的最大公约数的。

gcd函数的基本性质

       gcd( a , b )=gcd( b , a ) = gcd( -a , b )=gcd( |a| , |b| )

二、公式表述

gcd(a,b)=gcd(b,a mod b)

证明:

    a可以表示成a = kb + r,则r = a mod b

    假设da,b的一个公约数,则有d|a, d|b,r = a - kb,因此d|r

  (备注:因为da,b的一个公约数,所以我们将a换成 y * d,把b换成 x * d,则可以得到r=y*d-k*x*d,变为r=(y-k*x)*d,所以d | r)(可能是我自己太蠢了吧)

    因此d( b , a mod b)的公约数 

    假设d( b , a mod b)的公约数,则

    d | b , d |r ,但是a = kb +r(如上,我们可以把b和r换一下,则可以得出)

    因此d也是(a,b)的公约数 

    因此(a,b)(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

【C++代码实现】

   int gcd(int a,int b){

    return b?gcd(b,a%b):a;

  }

【pascal代码实现】

function gcd(a,b:longint):longint;

begin

    if b=0 then exit(a);

    gcd:=gcd(b,a mod b);

end;

【扩展算法】

       对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然

存在整数对 x,y ,使得 gcd(a,b)=ax+by。

【C++代码实现】   

int gcd(int a,int b,int &x,int &y){

    if (b==0){

        x=1,y=0;

        return a;

    }

    int q=gcd(b,a%b,y,x);

    y-=a/b*x;

    return q;

}

【pascal代码实现】

function gcd(a,b:longint; var x,y:longint):longint;

var t:longint;

begin

    if b=0 then

        begin

            x:=1; y:=0;

            exit(a);

        end;

    gcd:=gcd(b,a mod b,y,x);

    y:=y-(a div b)*x;

end;

求解 x,y的方法的理解

   设 a>b

   1   显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;

   2   a>b>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;

   也就是 ax1 + by1 = ay2 + b( x2 - [ a / b ] * y2);

   根据恒等定理得:x1= y2;  y1 = x2 - [ a / b ] * y2;

   这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.

   上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

扩展欧几里德算法是用来在已知a, b求解一组x,y使得ax+by = Gcd(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。

把这个实现和Gcd的递归实现相比,发现多了下面的x,y赋值过程,这就是扩展欧几里德算法的精髓。





LOFTER

让兴趣,更有趣

简单随性的记录
丰富多彩的内容
让生活更加充实

下载移动端
关注最新消息