「一本通 6.4 例 5」Strange Way to Express Integers - 省实信息学奥赛 - 在线练习

广东实验中学信息学奥赛评测系统

问题 2915. -- 「一本通 6.4 例 5」Strange Way to Express Integers

2915: 「一本通 6.4 例 5」Strange Way to Express Integers

时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p><strong>原题来自：<a href="http://poj.org/problem?id=2891">POJ 2891</a></strong></p>
<p>给定 <span class="katex"><span class="katex-mathml">2n2n</span><span class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">2</span><span class="mord mathit">n</span></span></span></span> 个正整数 <span class="katex"><span class="katex-mathml">a1,a2,⋯,ana_1,a_2,cdots ,a_n</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span> 和 <span class="katex"><span class="katex-mathml">m1,m2,⋯,mnm_1,m_2,cdots ,m_n</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">m</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">m</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">m</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>，求一个最小的正整数 <span class="katex"><span class="katex-mathml">xx</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">x</span></span></span></span>，满足 <span class="mjx-chtml"><span class="mjx-math"><span class="mjx-mrow"><span class="mjx-mi"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.372em; padding-bottom:0.372em;">∀</span></span><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.446em; padding-bottom:0.298em;">i</span></span><span class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.225em; padding-bottom:0.372em;">∈</span></span><span class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">[</span></span><span class="mjx-mn"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.372em; padding-bottom:0.372em;">1</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="margin-top:-0.144em; padding-bottom:0.519em;">,</span></span><span class="mjx-mi MJXc-space1"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">n</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">]</span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="margin-top:-0.144em; padding-bottom:0.519em;">,</span></span><span class="mjx-mi MJXc-space1"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">x</span></span><span class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.151em; padding-bottom:0.298em;">≡</span></span><span class="mjx-msubsup MJXc-space3"><span class="mjx-base"><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">a</span></span></span><span class="mjx-sub" style="font-size:70.7%; vertical-align:-0.212em; padding-right:0.071em;"><span class="mjx-mi" style=""><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.446em; padding-bottom:0.298em;">i</span></span></span></span><span class="mjx-mtext"><span class="mjx-char MJXc-TeX-main-R" style="margin-top:-0.291em; padding-bottom:0.372em;"> </span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">(</span></span><span class="mjx-mo" style="padding-left:0.278em; padding-right:0.278em;"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.372em; padding-bottom:0.372em;">mod</span></span><span class="mjx-msubsup"><span class="mjx-base"><span class="mjx-mi"><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.225em; padding-bottom:0.298em;">m</span></span></span><span class="mjx-sub" style="font-size:70.7%; vertical-align:-0.212em; padding-right:0.071em;"><span class="mjx-mi" style=""><span class="mjx-char MJXc-TeX-math-I" style="padding-top:0.446em; padding-bottom:0.298em;">i</span></span></span></span><span class="mjx-mtext"><span class="mjx-char MJXc-TeX-main-R" style="margin-top:-0.291em; padding-bottom:0.372em;"> </span></span><span class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R" style="padding-top:0.446em; padding-bottom:0.593em;">)</span></span></span></span></span>，或者给出无解。</p>
</div></div>

输入

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>多组数据。</p>
<p>每组数据第一行一个整数 <span class="katex"><span class="katex-mathml">nn</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span>；<br>接下来 <span class="katex"><span class="katex-mathml">nn</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 行，每行两个整数 <span class="katex"><span class="katex-mathml">mi,aim_i,a_i</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">m</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>。</p>
</div></div>

输出

提示

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><h4>样例输入</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">2
8 7
11 9</code></pre></div>
<h4>样例输出</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">31</code></pre></div>
</div></div>

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>对于全部数据，所有的输入都是非负的，并且可以用 <span class="katex"><span class="katex-mathml">6464</span><span class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">6</span><span class="mord mathrm">4</span></span></span></span> 位有符号整数表示。保证 <span class="katex"><span class="katex-mathml">1≤n≤105,mi>ai1le nle 10^5,m_igt a_i</span><span class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.008548em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">n</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord"><span class="mord mathrm">0</span><span class="vlist"><span style="top:-0.363em; margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">5</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">m</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span><span class="mrel">></span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em; margin-right:0.05em; margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>。</p>
</div></div>

标签

一本通提高篇 10213 扩展欧几里德算法中国剩余定理

[上一题][提交][讨论版][状态][下一题]

OI模式 | OJ模式 | 笔记本 | 如果发现题目有问题，请联系管理员：crxis@qq.com OIER
All Copyright Reserved 2010-2015 广东实验中学信息学奥赛评测系统 TEAM