【CF#338D】GCD Table
2024-09-04 17:13:10
【题目描述】
有一张N,M<=10^12的表格,i行j列的元素是gcd(i,j)
读入一个长度不超过10^4,元素不超过10^12的序列a[1..k],问是否在某一行中出现过
【题解】
要保证gcd(x,y)=a[i],显然x=lcm(a[1],a[2]……a[k])
然后y%a[1]=0,即(y+i-1)%a[i]=0
即y%a[1]=0
y%a[2]=-1
……
y%a[n]=-(n-1)
这就转化为了中国剩余定理
求出y之后,只需验证gcd(x,y+i-1)=a[i]即可
/*************
CF#338D
by chty
2016.11.3
*************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,m1,K,A,M,ans,lcm(),m[],a[];
inline ll read()
{
ll x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
if(b==) {x=; y=; g=a; return;}
exgcd(b,a%b,g,x,y);
ll t=x;x=y;y=t-a/b*y;
}
ll China()
{
for(ll i=;i<=K;i++) a[i]=-i;
A=a[],M=m[];
for(ll i=;i<=K;i++)
{
ll k,y,da=a[i]-A,g;
exgcd(M,m[i],g,k,y);
if(da%g) return -;
ll t=m[i]/g;
k*=da/g;
k=(k%t+t)%t;
A+=k*M;
M=M*m[i]/g;
A=(A+M)%M;
}
return A;
}
bool check()
{
if(lcm>n) return ;
ll ans=China();
if(ans<) return ;
if(ans==) ans=lcm;
if(ans+K->m1) return ;
for(ll i=;i<=K;i++) if(gcd(lcm,ans+i-)!=m[i]) return ;
return ;
}
int main()
{
//freopen("cin.in","r",stdin);
//freopen("cout.out","w",stdout);
n=read(); m1=read(); K=read();
for(ll i=;i<=K;i++) m[i]=read();
for(ll i=;i<=K;i++)
{
lcm=lcm/gcd(lcm,m[i])*m[i];
if(lcm>n) break;
}
check()?puts("YES"):puts("NO");
return ;
}
最新文章
- 参数*args和**args区别
- jQuery 学习笔记(函数调用机制)
- HTTP中缓存相关
- Angularjs简介
- jQuery入门第三
- 6.基于ZMQ的游戏网络层基础架构
- 锁定表头和固定列(Fixed table head and columns)
- Django启动报错笔记
- mac+php+nginx+laravel配置启动
- linux代码笔记
- python 绘图 异常点绘制使用 ax.plot(abnormal_points[&#39;ds&#39;], abnormal_points[&#39;y&#39;], ";rX";, label=&#39;abnormal points&#39;)
- 20.Scrapy日常练手
- IR Cut Filter
- Incorrect column count: expected 1, actual 5
- memcached 的配置及 spymemcached 客户端简单使用
- 【bzoj2085】[Poi2010]Hamsters Hash+倍增Floyd
- PostgreSQL 的日期函数用法举例
- HttpServlet容器响应Web客户流程
- 【BZOJ3697】采药人的路径(点分治)
- Javascript: 动态显示进度条
热门文章
- OpenCV-Python cv2.imdecode()和cv2.imencode() 图片解码和编码
- 【工作】to-do-list
- python库之threading
- hibernate正向工程生成数据库
- 【转】C# Socket编程(3)编码和解码
- 洛谷P3111 [USACO14DEC]牛慢跑Cow Jog_Sliver
- python中的单元测试pyUnit
- jQuery ajax submit form 被拦截问题的解决
- strtotime出现时区问题不一致的解决方法
- week01—绪论