forked from Lruihao/lruihao.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Euclid.html
317 lines (284 loc) · 64 KB
/
Euclid.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
<!DOCTYPE html><html class="theme-next pisces" lang="zh-CN,en,default"><head><meta name="baidu-site-verification" content="5rEIjow3aW"><meta name="google-site-verification" content="OhdtVOx5uwpZ_mMm0AZJXzw-dY1PPpAAkdavmmQhIL4"><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><script>!function(e,t,o,c,i,a,n){e.DaoVoiceObject=i,e[i]=e[i]||function(){(e[i].q=e[i].q||[]).push(arguments)},e[i].l=1*new Date,a=t.createElement(o),n=t.getElementsByTagName(o)[0],a.async=1,a.src=c,a.charset="utf-8",n.parentNode.insertBefore(a,n)}(window,document,"script",("https:"==document.location.protocol?"https:":"http:")+"//widget.daovoice.io/widget/0f81ff2f.js","daovoice"),daovoice("init",{app_id:"8a6701dd"}),daovoice("update")</script><link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=6.3.0" rel="stylesheet" type="text/css"><link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.3.0"><link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=6.3.0"><link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=6.3.0"><link rel="mask-icon" href="/images/logo.svg?v=6.3.0" color="#222"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",scheme:"Pisces",version:"6.3.0",sidebar:{position:"left",display:"post",offset:12,b2t:!1,scrollpercent:!0,onmobile:!0},fancybox:!0,fastclick:!1,lazyload:!0,tabs:!0,motion:{enable:!1,async:!1,transition:{post_block:"fadeIn",post_header:"slideDownIn",post_body:"slideDownIn",coll_header:"slideLeftIn",sidebar:"slideUpIn"}},algolia:{applicationID:"",apiKey:"",indexName:"",hits:{per_page:10},labels:{input_placeholder:"Search for Posts",hits_empty:"We didn't find any results for the search: ${query}",hits_stats:"${hits} results found in ${time} ms"}}}</script><meta name="description" content="转载注明，侵删题意：给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解个数。分析：对于解二元一次不定方程，容易想到利用扩展欧几里得求出一组可行解后找到通解，下面来介绍一下欧几里得以及扩展欧几里得。欧几里得：又名辗转相除法，是用来计算两个数的最大公约数，其中就是利用gcd(a,b)=gcd(b,a mod b)来求解。下证gcd(a,b"><meta name="keywords" content="ACM,数学,数论,欧几里得,他山之石"><meta property="og:type" content="article"><meta property="og:title" content="The equation-SGU106(扩展欧几里得)(转)"><meta property="og:url" content="https://lruihao.cn/Euclid.html"><meta property="og:site_name" content="博採眾長"><meta property="og:description" content="转载注明，侵删题意：给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解个数。分析：对于解二元一次不定方程，容易想到利用扩展欧几里得求出一组可行解后找到通解，下面来介绍一下欧几里得以及扩展欧几里得。欧几里得：又名辗转相除法，是用来计算两个数的最大公约数，其中就是利用gcd(a,b)=gcd(b,a mod b)来求解。下证gcd(a,b"><meta property="og:locale" content="zh-CN"><meta property="og:updated_time" content="2018-10-29T01:31:23.372Z"><meta name="twitter:card" content="summary"><meta name="twitter:title" content="The equation-SGU106(扩展欧几里得)(转)"><meta name="twitter:description" content="转载注明，侵删题意：给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解个数。分析：对于解二元一次不定方程，容易想到利用扩展欧几里得求出一组可行解后找到通解，下面来介绍一下欧几里得以及扩展欧几里得。欧几里得：又名辗转相除法，是用来计算两个数的最大公约数，其中就是利用gcd(a,b)=gcd(b,a mod b)来求解。下证gcd(a,b"><link rel="alternate" href="/atom.xml" title="博採眾長" type="application/atom+xml"><link rel="canonical" href="https://lruihao.cn/Euclid.html"><script type="text/javascript" id="page.configurations">CONFIG.page={sidebar:""}</script><title>The equation-SGU106(扩展欧几里得)(转) | 博採眾長</title><noscript><style type="text/css">.sidebar-inner,.use-motion .brand,.use-motion .collection-title,.use-motion .comments,.use-motion .menu-item,.use-motion .motion-element,.use-motion .pagination,.use-motion .post-block,.use-motion .post-body,.use-motion .post-header{opacity:initial}.use-motion .logo,.use-motion .site-subtitle,.use-motion .site-title{opacity:initial;top:initial}.logo-line-after i{right:initial}</style></noscript></head><body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-CN"><script type="text/javascript">console.log("\n` @@#``@@@@@@@@@@@@@@@@@@##,` \n` @@#`;@@@@@@@@@@@@@@@@@@@':' \n` @@#`@@@@@@@@@@@@@@@@@@@#+#;` \n` @@#`@@@@@@@@@@@@@@@@@@###@'. \n` @@+.@@@@@@@@@@@@@@@@@@@@@##, \n` @@#,@@@@@@@@@@@@@@@@@@@@@@#, \n` #@#:@@@@@@@@@@@@@@@@@@@@@@@, \n` #@#'@@@@@@@@@@@@@@@@@@@@@@@. \n` +@#;@@@@@@@@@@@@@@@@@@@@@@# \n` `;: ;@#'@@@@@@@@@@@@@@@@@@+'+@' \n` `,,;';'+';'@@+:@@@@@@@@@@@@##@#',.:#; \n,, `` ``..,:;@@#'@@@@@@@@#####@@@@#:`:. \n` `````:++@@@@@@@@@@@@@###@@@@#+,.. \n ``````.#@@@@@@@@@@@@@@#@@@#++#'`` \n` ```.,,:,.`:@@@@@@@@@@@@@###@@@##'.` \n``..`````..,::;+@@@@@@@@@@@@#+`::+##'`. \n` ````.```,@@@@@@@@@@@##;``.,';` ` \n``.;@@@@@@@@@@@@@@@@@@@@@@###;``..`````` \n#@@@@@@@@@@@@@@@@@@@@@@@@##@#;``,``,.`` \n@@@@@@@@@@@@@@@@@@@.`````..``.. +` `:` \n@+''++#####@@#`.@@@``````` ` `,``` `` \n';;;;'+##+'+.`;+@@@,..```` `` :,. \n;::,,:;+#++``,,#@@@'..``````` ,`.`` \n;,,,,...'#.,,..#@@@#,,.`````` .```` \n:,,,,....`,::;''+#@#;,..`````````.`` \n:,,,.....'##++''';:+':,.`..,,...` \n:,,,...#####+'+#@@@'.';+:. ` `` \n;,,.`'####'#,`.`+@@@+'``` `.` \n;,.`#@@@#+:'+++##+@##@,,,,` \n',.#@@###'''';:,.```,+#. \n+,#@@@####;,,..``````````````` `.:,::\n+@@@@###+;,,..`````````````````` `.,\n#@@@##+',,,........`````````````` \n@@@@#+:,,,,`........`````````` \n@@@#+:,,,,.`````.....`````````` `` \n@@##':,......`````....``` ````` ```\n@@@#':,....,..``````..```` ``` ```\n@@@#',....,,,..``````````` ``` ..\n@@@#,.....,,,,.`` ```````` `````` \n@@@+....,,,,,..````````````` `````````` \n@@@:....,,,,.LiRuihao```````` ```````````` \n#@@,....,,,,.Always Be Yourself !````````````\n,##,,...,::,.https://lruihao.cn ` `......``\n,'#,,..,,:::.`````````........`````` `.,,..\n\n您好！\n这里是李瑞豪的个人博客--博採眾長！\n我的主页是 https://ww.lruihao.cn\n\n\n")</script><div class="container sidebar-position-left page-post-detail"><div class="headband"></div><header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="header-inner"><script>function GetRandomNum(e,t){var n=t-e,r=Math.random();return e+Math.round(r*n)}function setSidebarMarginTop(e){return $("#sidebar").css({"margin-top":e})}function getHeaderOffset(){return $(".header-inner").height()+CONFIG.sidebar.offset}window.onload=function(){var e="不怕万人阻挡，只怕自己投降。W你如何回忆，决定你是一个怎样的人。W人生当苦无妨，良人当归即可。W逝者如斯乎，不舍昼夜。W你别出现在我黎明的梦里，我怕我醒来就抱不到你。W心向大佬，披荆斩棘。W兼收并蓄，博采众长。".split("W"),t=e[GetRandomNum(0,e.length-1)];$("#helloTitle").html(t),setSidebarMarginTop(getHeaderOffset())}</script><div class="site-brand-wrapper"><div class="site-meta"><div class="custom-logo-site-title"><a href="/" class="brand" rel="start"><span class="logo-line-before"><i></i></span> <span class="site-title" style="color:#ddd">博採眾長</span> <span class="logo-line-after"><i></i></span></a></div><p></p><p style="color:#555;font-family:STXK" class="site-subtitle" id="helloTitle" itemprop="description"></p><p></p></div><div class="site-nav-toggle"><button aria-label="切换导航栏"><span class="btn-bar"></span> <span class="btn-bar"></span> <span class="btn-bar"></span></button></div></div><nav class="site-nav"><ul id="menu" class="menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i><br>首页</a></li><li class="menu-item menu-item-lead"><a href="/home" rel="section"><i class="menu-item-icon fa fa-fw fa-paper-plane"></i><br>导航</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i><br>分类</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i><br>标签</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i><br>归档</a></li><li class="menu-item menu-item-guestbook"><a href="/guestbook/" rel="section"><i class="menu-item-icon fa fa-fw fa-book"></i><br>留言</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i><br>关于</a></li><li class="menu-item menu-item-search"><a href="javascript:;" class="popup-trigger"><i class="menu-item-icon fa fa-search fa-fw"></i><br>搜索</a></li></ul><div class="site-search"><div class="popup search-popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i> </span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"><input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"></div></div></div></nav></div></header><a href="https://github.com/Lruihao/lruihao.github.io" class="github-corner" target="_blank" title="万水千山总是情,给个star行不行！" aria-label="万水千山总是情,给个star行不行！" rel="external nofollow noopener noreferrer"><svg width="80" height="80" viewbox="0 0 250 250" style="fill:#222;color:#fff;position:absolute;top:0;border:0;right:0" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"/><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin:130px 106px" class="octo-arm"/><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"/></svg></a><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article"><div class="post-block"><link itemprop="mainEntityOfPage" href="https://lruihao.cn/Euclid.html"><span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person"><meta itemprop="name" content="李瑞豪"><meta itemprop="description" content="so far so good"><meta itemprop="image" content="/images/avatar.png"></span><span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization"><meta itemprop="name" content="博採眾長"></span><header class="post-header"><h2 class="post-title" itemprop="name headline">The equation-SGU106(扩展欧几里得)(转)</h2><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i> </span><span class="post-meta-item-text">发表于</span> <time title="创建时间：2018-08-10 10:32:39" itemprop="dateCreated datePublished" datetime="2018-08-10T10:32:39+08:00">2018-08-10</time> <span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-calendar-check-o"></i> </span><span class="post-meta-item-text">更新于</span> <time title="修改时间：2018-10-29 09:31:23" itemprop="dateModified" datetime="2018-10-29T09:31:23+08:00">2018-10-29</time> </span><span class="post-category"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-folder-o"></i> </span><span class="post-meta-item-text">分类于</span> <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/数学/" itemprop="url" rel="index"><span itemprop="name">数学</span></a></span> ， <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/数学/数论/" itemprop="url" rel="index"><span itemprop="name">数论</span></a></span> </span><span class="post-comments-count"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-comment-o"></i> </span><a href="/Euclid.html#comments" itemprop="discussionUrl"><span class="post-meta-item-text">评论数：</span> <span class="post-comments-count valine-comment-count" data-xid="/Euclid.html" itemprop="commentCount"></span> </a></span><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-eye"></i> 阅读次数： <span class="busuanzi-value" id="busuanzi_value_page_pv"></span> </span><span class="post-meta-divider">|</span> <span title="post.wordcount"><span class="post-meta-item-icon"><i class="fa fa-file-word-o"></i></span>字数： 2,064</span></div></header><div class="post-body" itemprop="articleBody"><p><strong><a href="https://www.cnblogs.com/Rinyo/archive/2012/11/25/2787419.html" rel="external nofollow noopener noreferrer" target="_blank">转载注明，侵删</a></strong></p><h3 id="题意："><a href="#题意：" class="headerlink" title="题意："></a>题意：</h3><p>给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解个数。</p><h3 id="分析："><a href="#分析：" class="headerlink" title="分析："></a>分析：</h3><p>对于解二元一次不定方程，容易想到利用扩展欧几里得求出一组可行解后找到通解，下面来介绍一下欧几里得以及扩展欧几里得。</p><h4 id="欧几里得："><a href="#欧几里得：" class="headerlink" title="欧几里得："></a>欧几里得：</h4><p>又名辗转相除法，是用来计算两个数的最大公约数，其中就是利用gcd(a,b)=gcd(b,a mod b)来求解。下证gcd(a,b)=gcd(b,a mod b)的正确性：</p><p>设a,b的一个公约数为d</p><p>设a mod b=r，则a=kb+r(k为整数)，r=a-kb</p><p>因为d|a,d|b</p><p>所以d|a-kb,即d|r，而r=a mod b</p><p>所以d为b,a mod b的公约数</p><p>又因为d也为a,b的公约数，所以（a,b)和(b,a mod b)的公约数一样，所以最大公约数必然一样，得证。</p><p>代码描述：<br></p><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">gcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (b==<span class="number">0</span>) <span class="keyword">return</span> a;</span><br><span class="line"> <span class="keyword">return</span> gcd(b,a%b);</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p><h4 id="扩展欧几里得"><a href="#扩展欧几里得" class="headerlink" title="扩展欧几里得"></a>扩展欧几里得</h4><p>顾名思义，为上述欧几里得算法的扩展。欧几里得是用来求a,b的最大公约数，那么扩展欧几里得不仅能求出a,b的最大公约数，还能求出满足ax+by=gcd(a,b)的一组可行解。<br>求解过程中，扩展欧几里得比欧几里得多了一个赋值过程，具体证明如下：</p><p>设ax1+by1=gcd(a,b),bx2+(a mod b)y2=gcd(b,a mod b)</p><p>因为由欧几里得算法可知，gcd(a,b)=gcd(b,a mod b)</p><p>所以ax1+by1=bx2+(a mod b)y2</p><p>因为<code>a mod b=a-(a div b)*b（div为整除</code></p><p>所以有<code>ax1+by1=bx2+(a-(a div b)*b)y2</code></p><p>将右边移项，展开得：<br></p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">ax1+by1=ay2+bx2-(a div b)*b*y2</span><br><span class="line"> =ay2+b[x2-(a div b)]y2</span><br></pre></td></tr></table></figure><p></p><p>所以可得：<br><code>x1=y2</code><br><code>y1=x2-(a div b)*y2</code></p><p>将得到的的x1,y1递归操作求解x2,y2，如此循环往复，将会像欧几里得一样得到b=0的情况，此时递归结束，返回x=1,y=0，回溯得解。</p><p>代码描述：</p><p>此函数返回的是a,b的最大公约数，同时也求解出满足ax+by=gcd(a,b)的一组可行的(x,y)</p><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">exgcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b,<span class="keyword">int</span> &x,<span class="keyword">int</span> &y)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (b==<span class="number">0</span>) {x=<span class="number">1</span>;y=<span class="number">0</span>;<span class="keyword">return</span> a;}</span><br><span class="line"> <span class="keyword">int</span> t=exgcd(b,a%b,x,y);</span><br><span class="line"> <span class="keyword">int</span> x0=x,y0=y;</span><br><span class="line"> x=y0;y=x0-(a/b)*y0;</span><br><span class="line"> <span class="keyword">return</span> t;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><h4 id="关于求解二元一次不定方程ax-by-c"><a href="#关于求解二元一次不定方程ax-by-c" class="headerlink" title="关于求解二元一次不定方程ax+by=c"></a>关于求解二元一次不定方程ax+by=c</h4><p>首先，如果c不是gcd(a,b)的倍数，方程显然无解。</p><p>扩展欧几里得求解的是ax+by=gcd(a,b)=1的可行解，但是题目中并没有说c与a,b互质之类的条件，所以需要在开始时两边同时除以gcd(a,b)。</p><p>设d=gcd(a,b)</p><p>设a’=a/d,b’=b/d,c’=c/d,</p><p>则下面需要求解a’x+b’y=c’的整数解，而gcd(a’,b’)=1，</p><p>则我们只需求a’x+b’y=1的可行解</p><p>直接使用扩展欧几里得，得到(x’,y’),则最终解为<code>x'*c',y'*c'</code>设为(x0,y0)。</p><p>现在得到了一组可行解，但是如何得到通解呢？</p><p>将(x0,y0)代入ax+by=c，则有</p><p><code>a*(x0)+b*(y0)=c</code></p><p>通过拆添项，可有：</p><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">a*(x0+1*b)+b*(y0-1*a)=c</span><br><span class="line"></span><br><span class="line">a*(x0+2*b)+b*(y0-2*a)=c</span><br><span class="line"></span><br><span class="line">a*(x0+3*b)+b*(y0-3*a)=c</span><br><span class="line"></span><br><span class="line">……</span><br></pre></td></tr></table></figure><p><code>a*(x0+k*b)+b*(y0-k*a)=c (k∈Z)</code></p><p>至此，我们得到了通解的方程</p><p><code>x=x0+k*b</code><br><code>y=y0-k*a (k∈Z)</code></p><p>这样，所有满足ax+by=c的可行解都可求出。</p><h3 id="具体实现"><a href="#具体实现" class="headerlink" title="具体实现"></a>具体实现</h3><p>有了主体算法，下面要谈到具体实现了。</p><h4 id="先处理一下无解的情况："><a href="#先处理一下无解的情况：" class="headerlink" title="先处理一下无解的情况："></a>先处理一下无解的情况：</h4><ol><li><p>当a=0并且b=0，而c≠0时，显然无解；<br>当a=0,b=0，而c=0时，[x1,x2],[y1,y2]都为可行解，根据乘法原理，可行解的个数为<code>(x2-x1+1)*(y2-y1+1)</code>;</p></li><li><p>当a=0 b≠0时：<br>此时即为求解by=c，则y=c/b，<br>如果c/b不是整数或c/b不在[y1,y2]的范围内，无解<br>否则[x1,x2]内全部整数都为可行解.</p></li><li><p>当b=0,a≠0时，同上。</p></li><li><p>若c不是gcd(a,b)的个数，方程显然无解。</p></li></ol><h4 id="处理完了一些繁琐的细节后，下面是具体的求解过程："><a href="#处理完了一些繁琐的细节后，下面是具体的求解过程：" class="headerlink" title="处理完了一些繁琐的细节后，下面是具体的求解过程："></a>处理完了一些繁琐的细节后，下面是具体的求解过程：</h4><ol><li><p>扩展欧几里得求解的是ax+by=c，而本题是ax+by+c=0，需将c移项。</p></li><li><p>对于本道题，首先要注意的是，对于负数的模运算在此算法中无法得到正确解，所以要处理一下a,b,c的正负情况。<br>如果a为负数，只需将a取相反数后，再处理一下x∈[x1,x2]的范围。当a取了相反数，相当于把x也取反，则需要把x的范围由[x1,x2]转变成[-x2,-x1],类似于把数轴反了过来。b同理。</p></li><li><p>利用扩展欧几里得解二元一次不定方程，得到一组可行解(x0,y0)。</p></li><li><p>因为题目中对x,y有条件约束，而有x=x0+kb,y=y0-kb，我们可以求出满足x∈[x1,x2],y∈[y1,y2]的k的取值范围,<br>即为求解x1<=x0+kb<=x2,y1<=y0-kb<=y2的整数k的个数<br>但是在求解这两个一次函数的过程中，会有除不尽的现象，该如何取整呢？</p></li></ol><p>举个例子</p><p>当出现2.5<=k<=5.5时，我们需要的可行的k为3,4,5，所以需要将2.5向上取整得到3，5.5向下取整得到5，即为3<=k<=5；</p><p>当出现-5.5<=<=-2.5时，我们需要的可行的k为-5,-4,-3,所以需要将-5.5向上取整得到-5,-2.5向下取整得到-3，即为-5<=k<=-3；</p><p>正负数的情况都已经考虑完全了，可以得到取整的结论：上界下取整，下界上取整。</p><p>最后，将得到的两个范围取交集，得到[l,r]，则最终答案为r-l+1。</p><p>这样，本题就可以完美解决了。</p><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// BY Rinyo</span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><cstdio></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><cmath></span></span></span><br><span class="line"><span class="keyword">long</span> <span class="keyword">long</span> a,b,c,x1,x2,yy1,y2,x0,yy0;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="title">cmin</span><span class="params">(<span class="keyword">const</span> <span class="keyword">long</span> <span class="keyword">long</span> &x,<span class="keyword">const</span> <span class="keyword">long</span> <span class="keyword">long</span> &y)</span> </span>{<span class="keyword">return</span> x<y?x:y;}</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="title">cmax</span><span class="params">(<span class="keyword">const</span> <span class="keyword">long</span> <span class="keyword">long</span> &x,<span class="keyword">const</span> <span class="keyword">long</span> <span class="keyword">long</span> &y)</span> </span>{<span class="keyword">return</span> x>y?x:y;}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">long</span> <span class="keyword">long</span> <span class="title">gcd</span><span class="params">(<span class="keyword">long</span> <span class="keyword">long</span> a,<span class="keyword">long</span> <span class="keyword">long</span> b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (b==<span class="number">0</span>) <span class="keyword">return</span> a;</span><br><span class="line"> <span class="keyword">return</span> gcd(b,a % b);</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">exgcd</span><span class="params">(<span class="keyword">long</span> <span class="keyword">long</span> a,<span class="keyword">long</span> <span class="keyword">long</span> b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (b==<span class="number">0</span>){x0=<span class="number">1</span>;yy0=<span class="number">0</span>;<span class="keyword">return</span>;}</span><br><span class="line"> exgcd(b,a%b);</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> t=x0;x0=yy0;yy0=t-a/b*yy0;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%I64d%I64d%I64d%I64d%I64d%I64d%I64d"</span>,&a,&b,&c,&x1,&x2,&yy1,&y2);</span><br><span class="line"> c=-c;</span><br><span class="line"> <span class="keyword">if</span> (c<<span class="number">0</span>) {a=-a;b=-b;c=-c;}</span><br><span class="line"> <span class="keyword">if</span> (a<<span class="number">0</span>) {a=-a;<span class="keyword">long</span> <span class="keyword">long</span> t=x1;x1=-x2;x2=-t;}</span><br><span class="line"> <span class="keyword">if</span> (b<<span class="number">0</span>) {b=-b;<span class="keyword">long</span> <span class="keyword">long</span> t=yy1;yy1=-y2;y2=-t;}</span><br><span class="line"> <span class="keyword">if</span> (a==<span class="number">0</span> && b==<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (c==<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%I64d"</span>,(x2-x1+<span class="number">1</span>)*(y2-yy1+<span class="number">1</span>));</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"0"</span>);<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (a==<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (c %b ==<span class="number">0</span>)</span><br><span class="line"> <span class="keyword">if</span> (c/b<=y2 && c/b>=yy1) {<span class="built_in">printf</span>(<span class="string">"%I64d"</span>,x2-x1+<span class="number">1</span>);<span class="keyword">return</span> <span class="number">0</span>;}</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"0"</span>);<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (b==<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (c%a==<span class="number">0</span>)</span><br><span class="line"> <span class="keyword">if</span> (c/a<=x2 && c/a>=x1) {<span class="built_in">printf</span>(<span class="string">"%I64d"</span>,y2-yy1+<span class="number">1</span>);<span class="keyword">return</span> <span class="number">0</span>;}</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"0"</span>);<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> d=gcd(a,b);</span><br><span class="line"> <span class="keyword">if</span> (c%d!=<span class="number">0</span>){<span class="built_in">printf</span>(<span class="string">"0"</span>);<span class="keyword">return</span> <span class="number">0</span>;}</span><br><span class="line"></span><br><span class="line"> a=a/d;b=b/d;c=c/d;</span><br><span class="line"> exgcd(a,b);</span><br><span class="line"> x0=x0*c;yy0=yy0*c;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">double</span> tx2=x2,tx1=x1,tx0=x0,ta=a,tb=b,tc=c,ty1=yy1,ty2=y2,ty0=yy0;</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> down1=<span class="built_in">floor</span>(((tx2-tx0)/tb)),down2=<span class="built_in">floor</span>(((ty0-ty1)/ta));</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> r=cmin(down1,down2);</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> up1=<span class="built_in">ceil</span>(((tx1-tx0)/tb)),up2=<span class="built_in">ceil</span>(((ty0-ty2)/ta));</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> l=cmax(up1,up2);</span><br><span class="line"> <span class="keyword">if</span> (r<l) <span class="built_in">printf</span>(<span class="string">"0"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%I64d"</span>,r-l+<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">}</span><br></pre></td></tr></table></figure><p>扩展欧几里得模板<br></p><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">exgcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b,<span class="keyword">int</span> &x,<span class="keyword">int</span> &y)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span>(b==<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> x=<span class="number">1</span>;</span><br><span class="line"> y=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">return</span> a;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> gcd=exgcd(b,a%b,x,y);</span><br><span class="line"> <span class="keyword">int</span> x2=x,y2=y;</span><br><span class="line"> x=y2;</span><br><span class="line"> y=x2-(a/b)*y2;</span><br><span class="line"> <span class="keyword">return</span> gcd;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"><span class="keyword">int</span> x,y,a,b;</span><br><span class="line"><span class="built_in">cout</span><<<span class="string">"请输入a和b:"</span><<<span class="built_in">endl</span>;</span><br><span class="line"><span class="built_in">cin</span>>>a>>b;</span><br><span class="line"><span class="built_in">cout</span><<<span class="string">"a和b的最大公约数:"</span><<<span class="built_in">endl</span>;</span><br><span class="line"><span class="built_in">cout</span><<exgcd(a,b,x,y)<<<span class="built_in">endl</span>;</span><br><span class="line"><span class="built_in">cout</span><<<span class="string">"ax+by=gcd(a,b) 的一组解是:"</span><<<span class="built_in">endl</span>;</span><br><span class="line"><span class="built_in">cout</span><<x<<<span class="string">" "</span><<y<<<span class="built_in">endl</span>;</span><br><span class="line"><span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p></div><div><div style="padding:10px 0;margin:20px auto;width:90%;text-align:center"><div>感谢支持！</div><button id="rewardButton" disable="enable" onclick="var qr = document.getElementById("QR"); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}"><span>打赏</span></button><div id="QR" style="display:none"><div id="wechat" style="display:inline-block"><img id="wechat_qr" src="/images/wechatpay.gif" alt="李瑞豪 微信支付"><p>微信支付</p></div><div id="alipay" style="display:inline-block"><img id="alipay_qr" src="/images/alipay.gif" alt="李瑞豪 支付宝"><p>支付宝</p></div></div></div></div><div><ul class="post-copyright"><li class="post-copyright-author"><strong>本文作者： </strong>李瑞豪</li><li class="post-copyright-link"><strong>本文链接：</strong> <a href="https://lruihao.cn/Euclid.html" title="The equation-SGU106(扩展欧几里得)(转)">https://lruihao.cn/Euclid.html</a></li><li class="post-copyright-license"><strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow noopener noreferrer" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！</li></ul></div><footer class="post-footer"><div class="post-tags"><a href="/tags/ACM/" rel="tag"><i class="fa fa-tag"></i> ACM</a> <a href="/tags/数学/" rel="tag"><i class="fa fa-tag"></i> 数学</a> <a href="/tags/数论/" rel="tag"><i class="fa fa-tag"></i> 数论</a> <a href="/tags/欧几里得/" rel="tag"><i class="fa fa-tag"></i> 欧几里得</a> <a href="/tags/他山之石/" rel="tag"><i class="fa fa-tag"></i> 他山之石</a></div><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/lightoj1282.html" rel="next" title="Leading and Trailing-lightoj1282(快速幂+对数运算)"><i class="fa fa-chevron-left"></i> Leading and Trailing-lightoj1282(快速幂+对数运算)</a></div><span class="post-nav-divider"></span><div class="post-nav-prev post-nav-item"><a href="/codeforces476b.html" rel="prev" title="Dreamoon and WiFi(组合数学)">Dreamoon and WiFi(组合数学) <i class="fa fa-chevron-right"></i></a></div></div></footer></div></article><div class="post-spread"></div></div></div><div class="comments" id="comments"></div></div><div class="sidebar-toggle"><div class="sidebar-toggle-line-wrap"><span class="sidebar-toggle-line sidebar-toggle-line-first"></span> <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span> <span class="sidebar-toggle-line sidebar-toggle-line-last"></span></div></div><aside id="sidebar" class="sidebar"><div id="sidebar-dimmer"></div><div class="sidebar-inner"><ul class="sidebar-nav motion-element"><li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">文章目录</li><li class="sidebar-nav-overview" data-target="site-overview-wrap">站点概览</li></ul><section class="site-overview-wrap sidebar-panel"><div class="site-overview"><div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person"><img class="site-author-image" itemprop="image" src="/images/avatar.png" alt="李瑞豪"><p class="site-author-name" itemprop="name">李瑞豪</p><p class="site-description motion-element" itemprop="description">so far so good</p></div><nav class="site-state motion-element"><div class="site-state-item site-state-posts"><a href="/archives/"><span class="site-state-item-count">96</span> <span class="site-state-item-name">日志</span></a></div><div class="site-state-item site-state-categories"><a href="/categories/index.html"><span class="site-state-item-count">20</span> <span class="site-state-item-name">分类</span></a></div><div class="site-state-item site-state-tags"><a href="/tags/index.html"><span class="site-state-item-count">56</span> <span class="site-state-item-name">标签</span></a></div></nav><div class="feed-link motion-element"><a href="/atom.xml" rel="alternate"><i class="fa fa-rss"></i> RSS</a></div><div class="links-of-author motion-element"><span class="links-of-author-item"><a href="https://github.com/Lruihao" target="_blank" title="GitHub" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-github"></i>GitHub</a> </span><span class="links-of-author-item"><a href="https://blog.csdn.net/qq_39520417" target="_blank" title="CSDN" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-contao"></i>CSDN</a> </span><span class="links-of-author-item"><a href="https://weibo.com/liahao" target="_blank" title="微博" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-weibo"></i>微博</a> </span><span class="links-of-author-item"><a href="/images/wechat.png" target="_blank" title="微信" rel="external nofollow"><i class="fa fa-fw fa-wechat"></i>微信</a> </span><span class="links-of-author-item"><a href="/images/qq.jpg" target="_blank" title="QQ" rel="external nofollow"><i class="fa fa-fw fa-qq"></i>QQ</a> </span><span class="links-of-author-item"><a href="mailto:[email protected]" target="_blank" title="E-Mail" rel="external nofollow"><i class="fa fa-fw fa-envelope"></i>E-Mail</a></span></div><div class="links-of-blogroll motion-element links-of-blogroll-inline"><div class="links-of-blogroll-title"><i class="fa fa-fw fa-globe"></i> 书签</div><ul class="links-of-blogroll-list"><li class="links-of-blogroll-item"><a href="/friends.html" title="友情链接" target="_blank">友情链接</a></li><li class="links-of-blogroll-item"><a href="/donators.html" title="赞助记录" target="_blank">赞助记录</a></li><li class="links-of-blogroll-item"><a href="/bugs.html" title="维护日志" target="_blank">维护日志</a></li><li class="links-of-blogroll-item"><a href="/links.html" title="收藏夹" target="_blank">收藏夹</a></li></ul></div></div></section><section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active"><div class="post-toc"><div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#题意："><span class="nav-number">1.</span> <span class="nav-text">题意：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分析："><span class="nav-number">2.</span> <span class="nav-text">分析：</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#欧几里得："><span class="nav-number">2.1.</span> <span class="nav-text">欧几里得：</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#扩展欧几里得"><span class="nav-number">2.2.</span> <span class="nav-text">扩展欧几里得</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#关于求解二元一次不定方程ax-by-c"><span class="nav-number">2.3.</span> <span class="nav-text">关于求解二元一次不定方程ax+by=c</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#具体实现"><span class="nav-number">3.</span> <span class="nav-text">具体实现</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#先处理一下无解的情况："><span class="nav-number">3.1.</span> <span class="nav-text">先处理一下无解的情况：</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#处理完了一些繁琐的细节后，下面是具体的求解过程："><span class="nav-number">3.2.</span> <span class="nav-text">处理完了一些繁琐的细节后，下面是具体的求解过程：</span></a></li></ol></li></ol></div></div></section></div></aside></div></main><footer id="footer" class="footer"><div class="footer-inner"><div class="copyright"><font color="black" face="STLiti">All Copyright Reserved </font><font color="black">©</font> <font color="black" face="STLiti"><span itemprop="copyrightYear">2018</span></font> <span class="with-love" id="animate"><i class="fa fa-heartbeat"></i> </span><span class="author" itemprop="copyrightHolder" style="font-family:MMT;font-size:120%;font-weight:700;color:#444">李瑞豪</span></div><div class="busuanzi-count"><script src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><font color="DarkSlateGray" face="STLiti"><span class="site-uv" title="总访客量"><i class="fa fa-user"></i> <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>人次<span class="post-meta-divider">|</span><i class="fa fa-edit" title="总字数"></i> <span class="post-count">48.2k</span>字, <span id="timeDate" title="网站运行时间">载入天数...</span><span id="times" title="网站运行时间">载入时分秒...</span><span class="post-meta-divider">|</span> </span></font><font color="DarkSlateGray" face="STLiti"><span class="site-pv" title="总访问量"><i class="fa fa-eye"></i> <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>次</span></font></div><div style="font-family:STLiti;display:inline-block;height:20px;line-height:20px"><a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=43030402000254" rel="external nofollow noopener noreferrer"><img src="/images/gov.png" style="float:left">湘公网安备 43030402000254号</a> <span class="post-meta-divider" style="color:#555">|</span><span><a href="http://www.miitbeian.gov.cn" target="_blank" rel="external nofollow noopener noreferrer">湘ICP备18020535号</a></span></div></div></footer><div class="back-to-top"><i class="fa fa-arrow-up"></i> <span id="scrollpercent"><span>0</span>%</span></div></div><script>var now=new Date;function createtime(){var n=new Date("05/28/2018 20:01:01");now.setTime(now.getTime()+250),days=(now-n)/1e3/60/60/24,dnum=Math.floor(days),hours=(now-n)/1e3/60/60-24*dnum,hnum=Math.floor(hours),1==String(hnum).length&&(hnum="0"+hnum),minutes=(now-n)/1e3/60-1440*dnum-60*hnum,mnum=Math.floor(minutes),1==String(mnum).length&&(mnum="0"+mnum),seconds=(now-n)/1e3-86400*dnum-3600*hnum-60*mnum,snum=Math.round(seconds),1==String(snum).length&&(snum="0"+snum),document.getElementById("timeDate").innerHTML=dnum+" 天",document.getElementById("times").innerHTML=hnum+" 时"+mnum+" 分"+snum+" 秒"}setInterval("createtime()",250)</script><script type="text/javascript" src="/js/src/night.js"></script><div class="cover"></div><script type="text/javascript" src="/js/src/crash_cheat.js"></script><script src="/js/src/activate-power-mode.js"></script><script>POWERMODE.colorful=!0,POWERMODE.shake=!1,document.body.addEventListener("input",POWERMODE)</script><canvas class="fireworks" style="position:fixed;left:0;top:0;z-index:1;pointer-events:none"></canvas><script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script><script type="text/javascript" src="/js/src/fireworks.js"></script><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script><script type="text/javascript" src="/js/src/utils.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/motion.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/affix.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/schemes/pisces.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/post-details.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=6.3.0"></script><script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script><script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script><script type="text/javascript">var GUEST=["nick","mail","link"],guest="nick,mail,link";guest=guest.split(",").filter(function(e){return-1<GUEST.indexOf(e)}),new Valine({av:AV,el:"#comments",verify:!1,notify:!1,appId:"7HwTRT0Q0Tfrat6ugrT6P67c-gzGzoHsz",appKey:"mhTY1kuUmviCtQwkwOASfsfD",placeholder:"ヾﾉ≧∀≦)o来啊，快活啊!填写邮箱能很快收到我的回复喔！",avatar:"monsterid",guest_info:guest,pageSize:"15"})</script><script type="text/javascript">// Popup Window;
var isfetched = false;
var isXml = true;
// Search DB path;
var search_path = "search.xml";
if (search_path.length === 0) {
search_path = "search.xml";
} else if (/json$/i.test(search_path)) {
isXml = false;
}
var path = "/" + search_path;
// monitor main search box;
var onPopupClose = function (e) {
$('.popup').hide();
$('#local-search-input').val('');
$('.search-result-list').remove();
$('#no-result').remove();
$(".local-search-pop-overlay").remove();
$('body').css('overflow', '');
}
function proceedsearch() {
$("body")
.append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
.css('overflow', 'hidden');
$('.search-popup-overlay').click(onPopupClose);
$('.popup').toggle();
var $localSearchInput = $('#local-search-input');
$localSearchInput.attr("autocapitalize", "none");
$localSearchInput.attr("autocorrect", "off");
$localSearchInput.focus();
}
// search function;
var searchFunc = function(path, search_id, content_id) {
'use strict';
// start loading animation
$("body")
.append('<div class="search-popup-overlay local-search-pop-overlay">' +
'<div id="search-loading-icon">' +
'<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
'</div>' +
'</div>')
.css('overflow', 'hidden');
$("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');
$.ajax({
url: path,
dataType: isXml ? "xml" : "json",
async: true,
success: function(res) {
// get the contents from search data
isfetched = true;
$('.popup').detach().appendTo('.header-inner');
var datas = isXml ? $("entry", res).map(function() {
return {
title: $("title", this).text(),
content: $("content",this).text(),
url: $("url" , this).text()
};
}).get() : res;
var input = document.getElementById(search_id);
var resultContent = document.getElementById(content_id);
var inputEventFunction = function() {
var searchText = input.value.trim().toLowerCase();
var keywords = searchText.split(/[\s\-]+/);
if (keywords.length > 1) {
keywords.push(searchText);
}
var resultItems = [];
if (searchText.length > 0) {
// perform local searching
datas.forEach(function(data) {
var isMatch = false;
var hitCount = 0;
var searchTextCount = 0;
var title = data.title.trim();
var titleInLowerCase = title.toLowerCase();
var content = data.content.trim().replace(/<[^>]+>/g,"");
var contentInLowerCase = content.toLowerCase();
var articleUrl = decodeURIComponent(data.url);
var indexOfTitle = [];
var indexOfContent = [];
// only match articles with not empty titles
if(title != '') {
keywords.forEach(function(keyword) {
function getIndexByWord(word, text, caseSensitive) {
var wordLen = word.length;
if (wordLen === 0) {
return [];
}
var startPosition = 0, position = [], index = [];
if (!caseSensitive) {
text = text.toLowerCase();
word = word.toLowerCase();
}
while ((position = text.indexOf(word, startPosition)) > -1) {
index.push({position: position, word: word});
startPosition = position + wordLen;
}
return index;
}
indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
});
if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
isMatch = true;
hitCount = indexOfTitle.length + indexOfContent.length;
}
}
// show search results
if (isMatch) {
// sort index by position of keyword
[indexOfTitle, indexOfContent].forEach(function (index) {
index.sort(function (itemLeft, itemRight) {
if (itemRight.position !== itemLeft.position) {
return itemRight.position - itemLeft.position;
} else {
return itemLeft.word.length - itemRight.word.length;
}
});
});
// merge hits into slices
function mergeIntoSlice(text, start, end, index) {
var item = index[index.length - 1];
var position = item.position;
var word = item.word;
var hits = [];
var searchTextCountInSlice = 0;
while (position + word.length <= end && index.length != 0) {
if (word === searchText) {
searchTextCountInSlice++;
}
hits.push({position: position, length: word.length});
var wordEnd = position + word.length;
// move to next position of hit
index.pop();
while (index.length != 0) {
item = index[index.length - 1];
position = item.position;
word = item.word;
if (wordEnd > position) {
index.pop();
} else {
break;
}
}
}
searchTextCount += searchTextCountInSlice;
return {
hits: hits,
start: start,
end: end,
searchTextCount: searchTextCountInSlice
};
}
var slicesOfTitle = [];
if (indexOfTitle.length != 0) {
slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
}
var slicesOfContent = [];
while (indexOfContent.length != 0) {
var item = indexOfContent[indexOfContent.length - 1];
var position = item.position;
var word = item.word;
// cut out 100 characters
var start = position - 20;
var end = position + 80;
if(start < 0){
start = 0;
}
if (end < position + word.length) {
end = position + word.length;
}
if(end > content.length){
end = content.length;
}
slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
}
// sort slices in content by search text's count and hits' count
slicesOfContent.sort(function (sliceLeft, sliceRight) {
if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
return sliceRight.searchTextCount - sliceLeft.searchTextCount;
} else if (sliceLeft.hits.length !== sliceRight.hits.length) {
return sliceRight.hits.length - sliceLeft.hits.length;
} else {
return sliceLeft.start - sliceRight.start;
}
});
// select top N slices in content
var upperBound = parseInt('1');
if (upperBound >= 0) {
slicesOfContent = slicesOfContent.slice(0, upperBound);
}
// highlight title and content
function highlightKeyword(text, slice) {
var result = '';
var prevEnd = slice.start;
slice.hits.forEach(function (hit) {
result += text.substring(prevEnd, hit.position);
var end = hit.position + hit.length;
result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
prevEnd = end;
});
result += text.substring(prevEnd, slice.end);
return result;
}
var resultItem = '';
if (slicesOfTitle.length != 0) {
resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
} else {
resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
}
slicesOfContent.forEach(function (slice) {
resultItem += "<a href='" + articleUrl + "'>" +
"<p class=\"search-result\">" + highlightKeyword(content, slice) +
"...</p>" + "</a>";
});
resultItem += "</li>";
resultItems.push({
item: resultItem,
searchTextCount: searchTextCount,
hitCount: hitCount,
id: resultItems.length
});
}
})
};
if (keywords.length === 1 && keywords[0] === "") {
resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
} else if (resultItems.length === 0) {
resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
} else {
resultItems.sort(function (resultLeft, resultRight) {
if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
return resultRight.searchTextCount - resultLeft.searchTextCount;
} else if (resultLeft.hitCount !== resultRight.hitCount) {
return resultRight.hitCount - resultLeft.hitCount;
} else {
return resultRight.id - resultLeft.id;
}
});
var searchResultList = '<ul class=\"search-result-list\">';
resultItems.forEach(function (result) {
searchResultList += result.item;
})
searchResultList += "</ul>";
resultContent.innerHTML = searchResultList;
}
}
if ('auto' === 'auto') {
input.addEventListener('input', inputEventFunction);
} else {
$('.search-icon').click(inputEventFunction);
input.addEventListener('keypress', function (event) {
if (event.keyCode === 13) {
inputEventFunction();
}
});
}
// remove loading animation
$(".local-search-pop-overlay").remove();
$('body').css('overflow', '');
proceedsearch();
}
});
}
// handle and trigger popup window;
$('.popup-trigger').click(function(e) {
e.stopPropagation();
if (isfetched === false) {
searchFunc(path, 'local-search-input', 'local-search-result');
} else {
proceedsearch();
};
});
$('.popup-btn-close').click(onPopupClose);
$('.popup').click(function(e){
e.stopPropagation();
});
$(document).on('keyup', function (event) {
var shouldDismissSearchPopup = event.which === 27 &&
$('.search-popup').is(':visible');
if (shouldDismissSearchPopup) {
onPopupClose();
}
});</script><script>!function(){var t=document.createElement("script"),e=window.location.protocol.split(":")[0];t.src="https"===e?"https://zz.bdstatic.com/linksubmit/push.js":"http://push.zhanzhang.baidu.com/push.js";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(t,s)}()</script><script src="/lib/pangu/dist/pangu.min.js?v=3.3"></script><script type="text/javascript">pangu.spacingPage()</script><style>.copy-btn{display:inline-block;padding:6px 12px;font-size:13px;font-weight:700;line-height:20px;color:#333;white-space:nowrap;vertical-align:middle;cursor:pointer;background-color:#eee;background-image:linear-gradient(#fcfcfc,#eee);border:1px solid #d5d5d5;border-radius:3px;user-select:none;outline:0}.highlight-wrap .copy-btn{transition:opacity .3s ease-in-out;opacity:0;padding:2px 6px;position:absolute;right:4px;top:8px}.highlight-wrap .copy-btn:focus,.highlight-wrap:hover .copy-btn{opacity:1}.highlight-wrap{position:relative}</style><script>$(".highlight").each(function(t,e){var n=$("<div>").addClass("highlight-wrap");$(e).after(n),n.append($("<button>").addClass("copy-btn").append("复制").on("click",function(t){var e=$(this).parent().find(".code").find(".line").map(function(t,e){return $(e).text()}).toArray().join("\n"),n=document.createElement("textarea");document.body.appendChild(n),n.style.position="absolute",n.style.top="0px",n.style.left="0px",n.value=e,n.select(),n.focus();var o=document.execCommand("copy");document.body.removeChild(n),o?$(this).text("复制成功"):$(this).text("复制失败"),$(this).blur()})).on("mouseleave",function(t){var e=$(this).find(".copy-btn");setTimeout(function(){e.text("复制")},300)}).append(e)})</script></body></html>