http://codeforces.com/problemset/problem/338/D

中国剩余定理的应用,思路是确定可能符合的最小行和最小列,然后判断是否符合。若不符合则后面的(最小的倍数)也不会符合。

寻找最小行和最小列就用了非互质中国剩余定理模版。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std; LL n,m,k,a[] = {},b[]; LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
} LL e_gcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x = ;
y = ;
return a;
}
LL ans = e_gcd(b,a%b,x,y),temp = x;
x = y;
y = temp-a/b*y;
return ans;
} LL CRT(LL *a,LL *m) //方程x%m=a;
{
LL lcm=,X=m[],Y=a[];
for(int i=;i<=k;i++) lcm=lcm/gcd(lcm,m[i])*m[i];
for(int i=;i<=k;i++)
{
LL A=X,B=m[i],d,x,y,c=a[i]-Y;
d=e_gcd(A,B,x,y);
if(c%d)return -;
LL mod=m[i]/d;
LL K=((x*c/d)%mod+mod)%mod;
Y=X*K+Y;
X=X*m[i]/d;
}
if(Y==) return lcm;
return Y;
} int main()
{
scanf("%I64d%I64d%I64d",&n,&m,&k);
for(int i = ;i <= k;i++) scanf("%I64d",&b[i]);
LL x = CRT(a,b);
if(x > n || x < )
{
printf("NO\n");
return ;
}
for(int i = ;i <= k;i++) a[i] = -i;
LL y = CRT(a,b);
if(y+k- > m || y < )
{
printf("NO\n");
return ;
}
for(int i = ;i <= k;i++)
{
if(gcd(x,y+i-) != b[i])
{
printf("NO\n");
return ;
}
}
printf("YES\n");
return ;
}

最新文章

  1. MySQL(MariaDB)的 SSL 加密复制
  2. JS相关环境搭建:Nodejs、karma测试框架、jsDuck、Express
  3. 使用 ServiceStack.Text 序列化 json 比Json.net更快
  4. ios 5
  5. 推荐5款超实用的.NET性能分析工具 转
  6. Matlab编程实例(2) 同期平均
  7. iOS实用技能扩展-静态库的制作与简单使用
  8. Linux安装 Mysql
  9. QueryError:Incorrect result size: expected 1, actual 0
  10. MYSQL的空间查询
  11. 微信小程序(四) 模板的使用
  12. C#导出 Excel 时, 生成 CheckBox 控件
  13. 别人的Linux私房菜(6)文件权限与目录配置
  14. Chart:Amcharts
  15. axios全局设置url公共请求头
  16. [Week17] 个人阅读作业
  17. Objecttive-C各种问题
  18. UEditor自定义toolbar工具条
  19. java线程池(一)
  20. nested exception is java.lang.VerifyError: Expecting a stackmap frame at bra

热门文章

  1. spring cloud微服务快速教程之(六) 应用监控 spring boot admin
  2. 应急响应&amp;&amp;取证
  3. AcWing 243. 一个简单的整数问题2 | 树状数组
  4. python打印图形
  5. MQ队列及常见操作
  6. vue vuex开发中遇到的问题及解决小技巧
  7. Redux 一步到位
  8. Filder配置及使用教程
  9. Flask蓝图(Blueprint)
  10. map转URL