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