题意:

给你n和k,表示有n个数,c1到cn,然后让你求一个数x,可以告诉你x%ci的值,问你是否可以唯一确定一个x%k的值

题解:

反证:

假设有两个x1,x2同时是解,则对于所有ci,x1%ci==x2%ci&&x1%k!=x2%k,及(x1-x2)%ci==0&&(x1-x2)%k!=0,

及x1-x2==nlcm(ci)(n属于1到无穷大),所以对于所有的n,nlcm(ci)%k!=0,显而易见所有的nlcm%k!=0的话,则lcm%k!=0,

所以可以得出存在两个解的话,lcm%k!=0

所以我们只要判断lcm%k是否等于零即可

#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" ";
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define ll long long
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pdd pair<double,double>
#define pdi pair<double,int>
#define mp(u,v) make_pair(u,v)
#define sz(a) a.size()
#define ull unsigned long long
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
#define db double
const int mod = 1e9+;
const int maxn = 1e6+;
const double eps = 1e-;
using namespace std;
bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }
bool ls(const db &a, const db &b) { return a + eps < b; }
bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }
ll gcd(ll a,ll b) { return a==?b:gcd(b%a,a); };
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll kpow(ll a,ll b) {ll res=;a%=mod; if(b<) return ; for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll read(){
ll x=,f=;char ch=getchar();
while (ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//inv[1]=1;
//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
int n,k;
ll c[maxn];
bool ok(){
ll ans = c[];
rep(i,,n+) ans = lcm(ans,c[i]) % k;
ans %= k;
return !ans;
}
int main(){
scanf("%d%d",&n,&k);
rep(i,,n+) scanf("%lld",&c[i]);
puts(ok()?"Yes":"No");
return ;
}

最新文章

  1. .NET应用架构设计—面向对象分析与设计四色原型模式(彩色建模、领域无关模型)(概念版)
  2. 嗅探、中间人sql注入、反编译--例说桌面软件安全性问题
  3. include指令和include标签的区别
  4. GET方法传递中文参数乱码解决办法
  5. class str
  6. hdu 1270 小希的数表
  7. linux read 用法
  8. mongo数据库使用小结
  9. vs2010 suite integration toolkit execution
  10. mysql安装常见问题(系统找不到指定的文件、发生系统错误 1067 进程意外终止)
  11. 关于 overridePendingTransition()使用
  12. js中运动框架的封装
  13. shell编程之环境变量配置文件(4)
  14. Solr中使用游标进行深度分页查询以提高效率(适用的场景下)
  15. 网络编程socket,详细讲述osi七层协议
  16. Linux下升级Python到3.5.2版本
  17. Linux uptime命令详解
  18. Mysql索引详解及优化(key和index区别)
  19. 《区块链100问》第73集:达世币Dash是什么?
  20. Python实现支付宝在线支付

热门文章

  1. 一个icon的选中与不选中
  2. luoguP1419 寻找段落(二分答案+单调队列)
  3. [洛谷P1343]地震逃生
  4. scrapy xpath选择器多级选择错误
  5. Android studio树形
  6. Python中的list,tuple,dict和set
  7. CountDownLatch &amp;amp; CyclicBarrier源代码实现解析
  8. vue28-2.0-过滤器
  9. Id选择器和Class选择器
  10. POJ 1895 分层图网络流+输出路径