CodeForces 687B Remainders Game
2024-10-19 00:24:34
数论。
如果$x$不唯一,假设存在两个解,较大的为${x_1}$,较小的为${x_2}$。
那么,
$\left\{ {\begin{array}{*{20}{c}}
{{x_1}\% {c_i} = {x_2}\% {c_i}}\\
{{x_1}\% k \ne {x_2}\% k}
\end{array}} \right. \Rightarrow \left\{ {\begin{array}{*{20}{c}}
{({x_1} - {x_2})\% {c_i} = 0}\\
{({x_1} - {x_2})\% k \ne 0}
\end{array}} \right.$。
$∵lcm({c_1},{c_2},{c_3},......,{c_n})\% {c_i} = 0$
$∴lcm({c_1},{c_2},{c_3},......,{c_n})\% ({x_1} - {x_2}) = 0$
$∵({x_1} - {x_2})\% k \ne 0$
$∴lcm({c_1},{c_2},{c_3},......,{c_n})\% k \ne 0$
也就是说:如果解不唯一,那么$lcm({c_1},{c_2},{c_3},......,{c_n})\% k \ne 0$。
换句话说就是:如果解唯一,那么$lcm({c_1},{c_2},{c_3},......,{c_n})\% k = 0$。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c = getchar(); x = ;while(!isdigit(c)) c = getchar();
while(isdigit(c)) { x = x * + c - ''; c = getchar(); }
} LL gcd(LL a,LL b)
{
if(b==) return a;
return gcd(b,a%b);
} LL lcm(LL a,LL b)
{
return a*b/gcd(a,b);
} int n;
LL ans=,k; int main()
{
scanf("%d%lld",&n,&k);
for(int i=;i<=n;i++)
{
LL x; scanf("%lld",&x);
ans=lcm(ans,x)%k;
}
if(ans) printf("No\n");
else printf("Yes\n"); return ;
}
最新文章
- 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest
- OAuth2.0 基础概述
- LCA和RMQ
- 静态方法和类成员方法(Python)
- hihoCoder#1015 : KMP算法 (KMP模板)
- WP8.1 添加启动画面
- richTextBoxFontClass
- 2.1 IDEA
- redis集群安装部署
- 201521123111《Java程序设计》第11周学习总结
- Selenium+Headless Firefox
- wait3和wait4函数(转)
- Linux中Postfix反病毒和垃圾邮件工具(十)
- 快速切题 poj1068
- beat冲刺(3/7)
- luoguP2735 电网 Electric Fences
- 一个";.java";的源文件中,是否可以包含多个类?(除了匿名内部类),有什么限制?
- uva 6957 Hyacinth bfs
- leetcode 213. 打家劫舍 II JAVA
- 集训考试题tents