-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
291 lines (272 loc) · 37.2 KB
/
index.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
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>Ptilopsis_w's little blog</title><meta name="author" content="Ptilopsis_w"><meta name="copyright" content="Ptilopsis_w"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta property="og:type" content="website">
<meta property="og:title" content="Ptilopsis_w's little blog">
<meta property="og:url" content="http://example.com/index.html">
<meta property="og:site_name" content="Ptilopsis_w's little blog">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://user-images.githubusercontent.com/99067091/196447950-e1bf3ac4-4cb0-41b5-86f5-50bf7bee2c3a.jpg">
<meta property="article:author" content="Ptilopsis_w">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://user-images.githubusercontent.com/99067091/196447950-e1bf3ac4-4cb0-41b5-86f5-50bf7bee2c3a.jpg"><link rel="shortcut icon" href="https://s1.328888.xyz/2022/06/09/zxPy7.jpg"><link rel="canonical" href="http://example.com/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: undefined,
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":200},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '天',
date_suffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
source: {
justifiedGallery: {
js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js',
css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css'
}
},
isPhotoFigcaption: false,
islazyload: false,
isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: 'Ptilopsis_w\'s little blog',
isPost: false,
isHome: true,
isHighlightShrink: false,
isToc: false,
postUpdate: '2022-11-29 16:54:12'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><meta name="generator" content="Hexo 6.0.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://user-images.githubusercontent.com/99067091/196447950-e1bf3ac4-4cb0-41b5-86f5-50bf7bee2c3a.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">56</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">6</div></a></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="page" id="body-wrap"><header class="full_page" id="page-header" style="background-image: url('https://user-images.githubusercontent.com/99067091/196380209-bc043e17-f91e-43ed-a02c-ec052971f539.png')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">Ptilopsis_w's little blog</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="site-info"><h1 id="site-title">Ptilopsis_w's little blog</h1><div id="site-subtitle"><span id="subtitle"></span></div></div><div id="scroll-down"><i class="fas fa-angle-down scroll-down-effects"></i></div></header><main class="layout" id="content-inner"><div class="recent-posts" id="recent-posts"><div class="recent-post-item"><div class="post_cover left"><a href="/2022/08/09/%E5%BF%AB%E8%AF%BB%E5%BF%AB%E5%86%99%E6%9D%BF%E5%AD%90/" title="快读快写板子"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/196374525-6b002aba-8200-4075-ad19-8b08765c5b73.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="快读快写板子"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/08/09/%E5%BF%AB%E8%AF%BB%E5%BF%AB%E5%86%99%E6%9D%BF%E5%AD%90/" title="快读快写板子">快读快写板子</a><div class="article-meta-wrap"><span class="article-meta"><i class="fas fa-thumbtack sticky"></i><span class="sticky">置顶</span><span class="article-meta-separator">|</span></span><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-08-09T08:57:10.047Z" title="发表于 2022-08-09 16:57:10">2022-08-09</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%A8%A1%E6%9D%BF/">模板</a></span></div><div class="content">v1.0
用法
通过 read() 和 print() 进行输入输出， 也可以用 cin , cout (我已经define了)。
千万不要快读快写和 cstdio 混用！！！！
read() 可以传入任意c++关键字类型和string(小数也可以)。
read() 和 print() 也可以传入多个参数，即使不同类型也可以。(c++98不支持)
int a; char b;read(a, b); // OK, no problem
输出小数时，使用setpcs(x)来保留精度(四舍五入)。
double x;print(setpcs(5), x);cout << setpcs(5) << x;
读入 char 类型时，会自动过滤掉空格(读入第一个不是空格的字符)，效果跟cin一样。
如果想要读入一整行，可以用getline(cin, string)(字符数组的我懒得写了)。
根据使用习惯也可以用 a = read<int>() 的方式读入。
read() 函数会返回成功读入了几个数据，可以用来判断是否到达读入文件结尾。
cin >> a ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2022/11/29/Tarjan%E4%B8%8E%E5%9B%BE%E8%BF%9E%E9%80%9A%E6%80%A7/" title="Tarjan与图连通性"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/196446812-1a7bd952-79ca-4c30-8ef4-a4622823257d.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Tarjan与图连通性"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/29/Tarjan%E4%B8%8E%E5%9B%BE%E8%BF%9E%E9%80%9A%E6%80%A7/" title="Tarjan与图连通性">Tarjan与图连通性</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-29T07:38:50.846Z" title="发表于 2022-11-29 15:38:50">2022-11-29</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E8%AF%BE%E4%BB%B6/">课件</a></span></div><div class="content">有向图强连通分量
简介
强连通分量定义: 在有向图 GGG 中，任意两个节点可以互相到达。
强连通分量（SCC）定义: 极大的强连通子图。
Tarjan 算法
我们先要学习一下 DFS 生成树：
有向图的 DFS 生成树主要有四种边：树边，返祖边，横叉边，前向边。
考虑 DFS 生成树与强连通分量的关系：如果节点 xxx 是某个强联通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其他节点肯定在搜索树中以 xxx 为根的子树中。
Tarjan 算法求强连通分量需要维护两个数组：
dfnxdfn_xdfnx ：DFS 时节点 xxx 被遍历的次序。
lowxlow_xlowx ：在 xxx 的子树中能回溯到的最早的在栈里的节点。
使用 DFS 对图中的所有节点进行搜索，维护每个节点的 dfndfndfn 和 lowlowlow 变量，且让搜索到的节点入栈。每找到一个强连通分量，就让这个强连通分量里所有节点出栈。在搜索过程中，对于节点 xxx 和 xxx 能直接到达的节点 yyy 考虑 333 中情况：
yyy 未被访问：继续对 yyy 进行搜索。在回溯过程中，用 lowyl ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2022/11/28/kruskal%E9%87%8D%E6%9E%84%E6%A0%91/" title="kruskal重构树"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/204221739-c6f196bc-8642-4dbb-8055-f7a64dd2dd5d.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="kruskal重构树"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/28/kruskal%E9%87%8D%E6%9E%84%E6%A0%91/" title="kruskal重构树">kruskal重构树</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-28T07:46:44.968Z" title="发表于 2022-11-28 15:46:44">2022-11-28</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E8%AF%BE%E4%BB%B6/">课件</a></span></div><div class="content">听着名字高大上，其实就是 kruskal MST 多加了一步而已。
构建方法
我们还是维持原来跑 kruskal MST 的过程：
首先新建 nnn 个集合，代表图上的每个点，点权都是 000。
每一次加边会合并两个集合，合并方法是新建一个点，点权为这次加入的边的边权，同时将两个集合的根节点分别设为新建点的左右儿子，然后合并成一个集合，根为新建点。
在进行 n−1n-1n−1 轮合并后，我们得到了恰有 nnn 个叶子的二叉树，同时每个非叶子节点都有两个儿子，这棵树就叫 kruskal 重构树。
这里套用一下 OI-Wiki 的图：
这张图的 kruskal 重构树为:
性质
原图中两点之间所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = kruskal 重构树上两点间 LCA 的权值。
例题
LOJ137 最小瓶颈路
题目求的就是两点间简单路径上最大边权的最小值，直接敲一个 kruskal 重构树再敲个 LCA 就行了。
NOI2018 归程
首先每条边有两个属性: 长度，海拔；因为这两个属性互不影响，而且家固定在节点 111，也就是终点固定， ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2022/11/14/2022-11-14%E6%80%BB%E7%BB%93/" title="2022-11-14总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/201649662-d0874551-11c7-4834-aeb1-815bd2aea3b8.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-14总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/14/2022-11-14%E6%80%BB%E7%BB%93/" title="2022-11-14总结">2022-11-14总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-14T11:33:13.666Z" title="发表于 2022-11-14 19:33:13">2022-11-14</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">鸽子要跑路
Description
鸽子一开始位于平面直角坐标系上的整点 (a,b)(a, b)(a,b)，每次可以上下左右走一个单位(保证坐标非负)。鸽子的家在 (c,d)(c,d)(c,d)。
鸽子的疲劳值初始值为 000。如果鸽子当前位置 (x,y)(x,y)(x,y) 满足 x and y>0x \, \operatorname{and} \, y > 0xandy>0，鸽子的疲劳值就要加 111，否则疲劳值不增加。and\operatorname{and}and 是按位与。起点与终点的疲劳值不计入答案。
求鸽子回家的最小疲劳值。
Input
第一行数据组数 TTT。
接下来 TTT 行，每行四个整数 a,b,c,da, b, c, da,b,c,d。
Output
TTT 行，每行一个整数表示答案。
Hint
T≤105,a,b,c,d≤1018T \le 10^5, a,b,c,d \le 10^{18}T≤105,a,b,c,d≤1018。
Solution
打个表可以发现，xandy=0x \operatorname{and} y = 0xand ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2022/11/12/2022-11-12%E6%80%BB%E7%BB%93/" title="2022-11-12总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/201472179-99b51708-ba99-43b5-b595-479f1f229a86.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-12总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/12/2022-11-12%E6%80%BB%E7%BB%93/" title="2022-11-12总结">2022-11-12总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-12T11:38:33.950Z" title="发表于 2022-11-12 19:38:33">2022-11-12</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">PolarSea 与边割集
Description
给定一棵 nnn 个点的无向树，边带权，树上每个点有三种状态：无归属、属于 SolarPea、属于 PolarSea。
SolarPea 和 PolarSea 想要断掉一些边，使得对于每一对点 (x,y)(x,y)(x,y)，若 xxx 属于 SolarPea，yyy 属于 PolarSea，则 x,yx,yx,y 不连通。
求断掉的边的最小权值和。
Input
第一行包含一个整数 nnn。
接下来 n−1n-1n−1 行，每行包含三个数 u,v,wu,v,wu,v,w， 表示一条连接 u,vu,vu,v，权值为 www 的边。保证给出的是一棵树。
接下来一行，首先包含一个数 sss，表示属于 SolarPea 的点数。接下来 sss 个不同的数 a1,⋯ ,asa_1,\cdots,a_sa1,⋯,as，表示所有属于 SolarPea 的点。
接下来一行，首先包含一个数 ppp，表示属于 PolarSea 的点数。接下来 ppp 个不同的数 b1,⋯ ,bpb_1,\cdots,b_pb1,⋯,bp，表示所有属于 Polar ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2022/11/11/2022-11-11%E6%80%BB%E7%BB%93/" title="2022-11-11总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/201289478-1312e8b4-8294-4dc0-9d2f-eb8742308f32.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-11总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/11/2022-11-11%E6%80%BB%E7%BB%93/" title="2022-11-11总结">2022-11-11总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-11T07:45:23.807Z" title="发表于 2022-11-11 15:45:23">2022-11-11</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">序列
Description
小 Y 酷爱的接龙游戏正是这样。玩腻了成语接龙之后，小 决定尝试无平方因子二元合数接龙，规则如下： 现有 nnn 个不超过 10610^6106 的合数，每个均可表示为 a=pqa=pqa=pq ( p,qp,qp,q 为两个互异素数)。 若 a=p1q1(p1<q1)a=p_1 q_1 (p_1 < q_1)a=p1q1(p1<q1) , b=p2q2(p2<q2)b=p_2 q_2(p_2 < q_2)b=p2q2(p2<q2) ，当且仅当 q1=p2q_1 = p_2q1=p2 时 bbb 能接在 aaa 后面。 请问从给定的这 nnn 个数中选数接龙，最长可以形成一个包含多少数的接龙序列？
Input
第一行输入一个正整数 nnn, 意义如题干所述。
第二行输入 nnn 个不超过 10610^6106 的合数。
Output
输出一个整数表示答案。
Hint
n≤5×104n \le 5 \times 10^4n≤5×104。
Solution
把一个数 a=pqa = p qa=pq 看成 ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2022/11/10/2022-11-10%E6%80%BB%E7%BB%93/" title="2022-11-10总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/201096715-a828b90d-2755-4869-b7d9-23f5dfd5ba31.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-10总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/10/2022-11-10%E6%80%BB%E7%BB%93/" title="2022-11-10总结">2022-11-10总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-10T12:56:40.702Z" title="发表于 2022-11-10 20:56:40">2022-11-10</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">GCD 和 LCM
Description
TTT 个询问，每次询问给出三个整数 n,m,an, m, an,m,a，求：
∑i=1n∑j=1mlcm(i,j)[gcd(i,j)≤a]\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i,j) [\gcd(i,j) \le a]
i=1∑nj=1∑mlcm(i,j)[gcd(i,j)≤a]
Input
第一行读入 TTT。
接下来 TTT 行，每行三个整数 n,m,an, m, an,m,a。
Output
TTT 行，表示每个询问的答案。
Hint
T≤104,n,m,a≤105T \le 10^4, n,m,a \le 10^5T≤104,n,m,a≤105
Solution
套路莫比乌斯反演，下面设 n≤mn \le mn≤m。
∑i=1n∑j=1mlim(i,j)[gcd(i,j)≤a]=∑d=1min(n,a)1d∑i=1n∑i=1mij[gcd(i,j)=d]=∑d=1min(n,a)d∑i=1⌊nd⌋∑j=1⌊md⌋ij[gcd(i,j)=1]=∑d=1m ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2022/11/10/2022-11-9%E6%80%BB%E7%BB%93/" title="2022-11-9总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/201096948-299c137b-8473-45c9-9d13-d8f39d103132.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-9总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/10/2022-11-9%E6%80%BB%E7%BB%93/" title="2022-11-9总结">2022-11-9总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-10T12:56:24.000Z" title="发表于 2022-11-10 20:56:24">2022-11-10</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">精神焕发
Description
给出一棵 nnn 个点的树，点从 111 至 nnn 编号。每个点 uuu 上有足够多瓶加血 wuw_uwu 的药水，如果原来你的血量为 xxx*，那么喝下这瓶药水后你的血量会变为 x+wux+w_ux+wu。
有 qqq 次询问。每次询问给出数 xxx 与两个点的编号 sss、ttt。
这次询问中，你的初始血量为 xxx，一开始在 sss，想要走到 ttt。每次走到一个点，你就会喝下这个点上的药水（一开始来到点 sss 时会喝下 sss 上的药水）。你可以多次经过一个点，每次经过时都会喝下一瓶这个点上的药水。如果某个时刻你的血量小于 000，那么你就死了。你想知道你是否可以在不死的情况下从 sss 走到 ttt。
更形式化地，你需要判断是否存在一个点的编号组成的序列 p1…kp_{1 \dots k}p1…k，满足：
p1=sp_1=sp1=s，pk=tp_k=tpk=t；
对于任意 i∈[1,k−1]i \in [1,k-1]i∈[1,k−1]，树上的点 pip_ipi 与 pi+1p_{i+1}pi+1 之间有一条边。
对于任意 ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2022/11/08/2022-11-8%E6%80%BB%E7%BB%93/" title="2022-11-8总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/200542536-82a34e2a-b359-4d2e-bca1-b19cd7439c1d.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-8总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/08/2022-11-8%E6%80%BB%E7%BB%93/" title="2022-11-8总结">2022-11-8总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-08T10:36:17.516Z" title="发表于 2022-11-08 18:36:17">2022-11-08</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">环
Description
对于一个长度为 nnn 的 010101 串，下标从 000 到 n−1n-1n−1 。定义两种类型的操作：
A类型：选择一个 xxx，将序列循环右移 xxx 位，也就是新序列的第 (i+x) mod n(i+x) \bmod n(i+x)modn 位对应原序列的第 iii 位。
B类型：选择一个 xxx ，满足序列的第 xxx 个位置位 111 ，且第 (x+1) mod n(x+1) \bmod n(x+1)modn 位不为 111 ，交换序列的第 xxx 个位置和第 (x+1) mod n(x+1) \bmod n(x+1)modn 个位置的字符。
给定 n,k,ln,k,ln,k,l 。请构造一个由 lll 个长度为 nnn 的 010101 串构成的序列 SSS，下标从 000 开始。使得序列中每个串恰好有 kkk 个 111 。且对于 0≤i<l−10 \le i < l-10≤i<l−1，SiS_iSi 既可以通过一次A类型的操作，也可以通过一次B类型的操作，变为 Si+1S_{i+1}Si+1。
Input
第一行一个整 ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2022/11/06/2022-11-5%E6%80%BB%E7%BB%93/" title="2022-11-5总结"><img class="post_bg" src="https://user-images.githubusercontent.com/99067091/200146769-0dacec04-4726-40d1-9e70-9f07da15ed8b.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-5总结"></a></div><div class="recent-post-info"><a class="article-title" href="/2022/11/06/2022-11-5%E6%80%BB%E7%BB%93/" title="2022-11-5总结">2022-11-5总结</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time datetime="2022-11-06T03:30:14.029Z" title="发表于 2022-11-06 11:30:14">2022-11-06</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E6%80%BB%E7%BB%93/">总结</a></span></div><div class="content">军训
Description
起点 (0,0)(0,0)(0,0) ，每次只能走恰好曼哈顿距离为 kkk 的点，构造一种到达 (x,y)(x,y)(x,y) 且步数最小的方案，无解输出 -1。
Input
一行三个整数 k,x,yk, x, yk,x,y 。
Output
若无解，一行一个整数 -1。
否则第一行一个整数 sss, 代表最小操作次数。
接下来 sss 行，第 iii 行两个整数 xi,yix_i, y_ixi,yi, 表示第 iii 次操作后的坐标，若多组解任意输出一组。
Hint
1≤k≤109,−105≤x,y≤105,(x,y)≠(0,0)1 \le k \le 10^9, -10^5 \le x,y \le 10^5, (x,y) \not = (0,0)1≤k≤109,−105≤x,y≤105,(x,y)=(0,0)
Solution
因为 x,yx,yx,y 可正可负，不如先将 x,yx,yx,y 取绝对值，输出时判符号。
如果 kkk 是奇数，那么所有坐标都可达(存在一种方案从 (x,y)(x,y)(x,y) 走到 (x+1,y)(x+1,y)(x ...</div></div></div><nav id="pagination"><div class="pagination"><span class="page-number current">1</span><a class="page-number" href="/page/2/#content-inner">2</a><span class="space">…</span><a class="page-number" href="/page/6/#content-inner">6</a><a class="extend next" rel="next" href="/page/2/#content-inner"><i class="fas fa-chevron-right fa-fw"></i></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://user-images.githubusercontent.com/99067091/196447950-e1bf3ac4-4cb0-41b5-86f5-50bf7bee2c3a.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">Ptilopsis_w</div><div class="author-info__description"></div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">56</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">6</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/Ptilopsisw"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">建议科学上网，否则加载图片会很慢。</div></div><div class="sticky_layout"><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2022/11/29/Tarjan%E4%B8%8E%E5%9B%BE%E8%BF%9E%E9%80%9A%E6%80%A7/" title="Tarjan与图连通性"><img src="https://user-images.githubusercontent.com/99067091/196446812-1a7bd952-79ca-4c30-8ef4-a4622823257d.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Tarjan与图连通性"/></a><div class="content"><a class="title" href="/2022/11/29/Tarjan%E4%B8%8E%E5%9B%BE%E8%BF%9E%E9%80%9A%E6%80%A7/" title="Tarjan与图连通性">Tarjan与图连通性</a><time datetime="2022-11-29T07:38:50.846Z" title="发表于 2022-11-29 15:38:50">2022-11-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/11/28/kruskal%E9%87%8D%E6%9E%84%E6%A0%91/" title="kruskal重构树"><img src="https://user-images.githubusercontent.com/99067091/204221739-c6f196bc-8642-4dbb-8055-f7a64dd2dd5d.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="kruskal重构树"/></a><div class="content"><a class="title" href="/2022/11/28/kruskal%E9%87%8D%E6%9E%84%E6%A0%91/" title="kruskal重构树">kruskal重构树</a><time datetime="2022-11-28T07:46:44.968Z" title="发表于 2022-11-28 15:46:44">2022-11-28</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/11/14/2022-11-14%E6%80%BB%E7%BB%93/" title="2022-11-14总结"><img src="https://user-images.githubusercontent.com/99067091/201649662-d0874551-11c7-4834-aeb1-815bd2aea3b8.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-14总结"/></a><div class="content"><a class="title" href="/2022/11/14/2022-11-14%E6%80%BB%E7%BB%93/" title="2022-11-14总结">2022-11-14总结</a><time datetime="2022-11-14T11:33:13.666Z" title="发表于 2022-11-14 19:33:13">2022-11-14</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/11/12/2022-11-12%E6%80%BB%E7%BB%93/" title="2022-11-12总结"><img src="https://user-images.githubusercontent.com/99067091/201472179-99b51708-ba99-43b5-b595-479f1f229a86.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-12总结"/></a><div class="content"><a class="title" href="/2022/11/12/2022-11-12%E6%80%BB%E7%BB%93/" title="2022-11-12总结">2022-11-12总结</a><time datetime="2022-11-12T11:38:33.950Z" title="发表于 2022-11-12 19:38:33">2022-11-12</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/11/11/2022-11-11%E6%80%BB%E7%BB%93/" title="2022-11-11总结"><img src="https://user-images.githubusercontent.com/99067091/201289478-1312e8b4-8294-4dc0-9d2f-eb8742308f32.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022-11-11总结"/></a><div class="content"><a class="title" href="/2022/11/11/2022-11-11%E6%80%BB%E7%BB%93/" title="2022-11-11总结">2022-11-11总结</a><time datetime="2022-11-11T07:45:23.807Z" title="发表于 2022-11-11 15:45:23">2022-11-11</time></div></div></div></div><div class="card-widget card-categories"><div class="item-headline">
<i class="fas fa-folder-open"></i>
<span>分类</span>
</div>
<ul class="card-category-list" id="aside-cat-list">
<li class="card-category-list-item "><a class="card-category-list-link" href="/categories/VSCode%E6%8F%92%E4%BB%B6/"><span class="card-category-list-name">VSCode插件</span><span class="card-category-list-count">2</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E5%8D%9A%E5%AE%A2/"><span class="card-category-list-name">博客</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/"><span class="card-category-list-name">学习笔记</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E6%80%BB%E7%BB%93/"><span class="card-category-list-name">总结</span><span class="card-category-list-count">43</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E6%A8%A1%E6%9D%BF/"><span class="card-category-list-name">模板</span><span class="card-category-list-count">5</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E8%AF%BE%E4%BB%B6/"><span class="card-category-list-name">课件</span><span class="card-category-list-count">4</span></a></li>
</ul></div><div class="card-widget card-archives"><div class="item-headline"><i class="fas fa-archive"></i><span>归档</span></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2022/11/"><span class="card-archive-list-date">十一月 2022</span><span class="card-archive-list-count">15</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2022/10/"><span class="card-archive-list-date">十月 2022</span><span class="card-archive-list-count">15</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2022/09/"><span class="card-archive-list-date">九月 2022</span><span class="card-archive-list-count">16</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2022/08/"><span class="card-archive-list-date">八月 2022</span><span class="card-archive-list-count">10</span></a></li></ul></div><div class="card-widget card-webinfo"><div class="item-headline"><i class="fas fa-chart-line"></i><span>网站资讯</span></div><div class="webinfo"><div class="webinfo-item"><div class="item-name">文章数目 :</div><div class="item-count">56</div></div><div class="webinfo-item"><div class="item-name">已运行时间 :</div><div class="item-count" id="runtimeshow" data-publishDate="2022-02-01T16:00:00.000Z"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">本站访客数 :</div><div class="item-count" id="busuanzi_value_site_uv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">本站总访问量 :</div><div class="item-count" id="busuanzi_value_site_pv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">最后更新时间 :</div><div class="item-count" id="last-push-date" data-lastPushDate="2022-11-29T08:54:11.215Z"><i class="fa-solid fa-spinner fa-spin"></i></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">©2020 - 2022 By Ptilopsis_w</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.min.js"></script><div class="js-pjax"><script>function subtitleType () {
if (true) {
window.typed = new Typed("#subtitle", {
strings: ["Never gonna give you up","Never gonna let you down","Welcome"],
startDelay: 300,
typeSpeed: 150,
loop: false,
backSpeed: 50
})
} else {
document.getElementById("subtitle").innerHTML = 'Never gonna give you up'
}
}
if (true) {
if (typeof Typed === 'function') {
subtitleType()
} else {
getScript('https://cdn.jsdelivr.net/npm/typed.js/lib/typed.min.js').then(subtitleType)
}
} else {
subtitleType()
}</script></div><script defer="defer" id="fluttering_ribbon" mobile="false" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/canvas-fluttering-ribbon.min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>