I can't do anything but study number theory QAQ

I don't want to post the original English title

The question :

There is a N*M Table for ,i That's ok j The element of the column is gcd(i,j)
Read in a length of k, The element size does not exceed 10^12 Sequence a[1..k], Ask if the sequence has ever appeared in a row of the table

1<=N,M<=10^12
1<=k<=10^4

Okay

First of all, obviously x=lcm(a[i])

then (y+i-1)%a[i]==0

namely y%[i]=1-n

And then it magically becomes the Chinese remainder theorem

Find out x and y If there is no solution, then , There's a lot going on

First of all, if x and y exceed n,m The scope of or <0 Obviously not

Then notice the enumeration i see gcd(x,y+i-1) Is it equal to a[i]

Okay ? It doesn't seem to be much

Note that because the expression is directly defined, it is not actually given out , therefore n,m You can int burst

All the calculations require longlong?

I can't do anything but study number theory QAQ

Code :

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
ll rd(){ll z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
ll n,m,o; ll mo[],a[];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=,y=; return a;}
ll d=exgcd(b,a%b,x,y);
ll tmp=x; x=y,y=tmp-a/b*y;
return d;
}
ll chn(){
ll M=mo[],A=a[],k,y;
for(int i=;i<=o;++i){
ll tmp=a[i]-A,d=exgcd(M,mo[i],k,y);
if(tmp%d) return -;
ll tm=mo[i]/d;
k=(k*tmp/d%tm+tm)%tm,A+=k*M,M=M*mo[i]/d,A=(A+M)%M;
}
return A;
}
int main(){freopen("ddd.in","r",stdin);
cin>>n>>m>>o;
for(int i=;i<=o;++i) mo[i]=rd(),a[i]=-i;
int y=chn();
ll x=,d;
for(int i=;i<=o;++i){
d=exgcd(x,mo[i],d,d);
x=x*mo[i]/d;
}
if(!y) y=x;
if(y< || y+o->m || x>n){ cout<<"NO"<<endl; return ;}
for(int i=;i<=o;++i)if(exgcd(x,y+i-,d,d)!=mo[i]){ cout<<"NO"<<endl; return ;}
cout<<"YES"<<endl;
return ;
}

codeforces 338D GCD Table More articles about

  1. Codeforces 338D GCD Table Chinese remainder theorem

    Topic links : Click to open the link given n*m matrix ,[i,j] The score is gcd(i,j) Given a k Long sequence , Ask if it matches The continuity of a row of a matrix k Elements Ideas : We asked for a solution (i,j) bring i<=n &am ...

  2. codeforces 582A. GCD Table Problem solving report

    Topic link :http://codeforces.com/problemset/problem/582/A There are many questions on the Internet , Don't say , Post code directly = = Official explanation : http://codeforces.com ...

  3. CodeForces - 583C GCD Table map Of auto Traverse , A little greedy thinking

    The question : Here you are. n*n gcd All the numbers in the table ( In any order ) , Find... On the diagonal n What are the numbers .gcd The table is defined as follows , First the n Fill in the number on the diagonal , Then fill each grid with the number on the corresponding diagonal gcd value , That is to say V[i][j]=gc ...

  4. CF#338D. GCD Table

    Portal Simple practice of Chinese remainder theorem . First of all, the number of lines must be $lcm$, Then as long as we determine the minimum number of columns, we can determine whether the solution is legal . We can get a system of linear modular equations : $y \equiv 0 \pmod{a_1}$ $y+1 \equ ...

  5. codeforces 582A GCD Table

    Brief introduction : Given a length of $n$ Sequence Take the numbers in this sequence $gcd$ obtain $n^2$ Number Will this $n^2$ The number is out of order A possible case of finding the original sequence ------------------------- ...

  6. Codeforces Round #323 (Div. 2) C. GCD Table violence

    C. GCD Table Time Limit: 1 Sec Memory Limit: 256 MB Topic linking http://codeforces.com/contest/583/problem/C ...

  7. Codeforces Round #323 (Div. 2) C. GCD Table map

    Topic link :http://codeforces.com/contest/583/problem/C C. GCD Table time limit per test 2 seconds memory l ...

  8. Codeforces Round #323 (Div. 2) C.GCD Table

    C. GCD Table The GCD table G of size n × n for an array of positive integers a of length n is define ...

  9. Codeforces Round #323 (Div. 1) A. GCD Table

    A. GCD Table time limit per test 2 seconds memory limit per test 256 megabytes input standard input ...

Random recommendation

  1. Learning notes _Java_day14— Coding of actual combat ___ The whole process of a registration page

  2. In depth understanding of offsetTop And offsetLeft

    As I'm on my way to the front, I'm not going back , I used to think that offsetTop Is the left border of the element to the containing element offsetParent The pixel distance between the left inner borders of , Empathy offsetRight It's relative to the top inner border . So here comes the question , Contains elements off ...

  3. WebApi2 Learning records on the official website --- Authentication And Authorization

    Authentication( authentication )   WebAPI The authentication in can use HttpModel You can also use HTTP message handler, Specific use which can refer to the basis : One HttpModel Sure ...

  4. Unique Binary Search Trees,Unique Binary Search Trees II

    Unique Binary Search Trees Total Accepted: 69271 Total Submissions: 191174 Difficulty: Medium Given  ...

  5. ubuntu System opencv3.1.0 install

    opencv Compilation and installation Compile environment installation : sudo apt-get install build-essential Required package installation : sudo apt-get install cmake git libgtk ...

  6. ios System ipa file Detailed explanation of packaging process And Handling of common problems

    notes : Think about it first , I was going to write one article a day , Make a little progress every day , But I've been lazy lately , It hasn't been updated for three days , I would like to warn you and myself , Programmers need to be disciplined , Technology needs persistence , You can't fish for three days , Two days outside . Now let's move on to the theme , Used a while ago xco ...

  7. linux Next vim Editor use

    VIM - Vi IMproved: vim yes vi An updated version of the editor , yes linux Next Standard Editor , Have programming ability , You can distinguish the correctness of grammar according to the font color , Convenient program design . Use : # vim [OPTION] ...

  8. WebStorm Repeat code, express quickly

    One , problem Usually use WebStorm You need a lot of references to js, There's a lot of duplicate code , Write the same code many times at a time , So how to simply write repeated code through a few shortcut keys ? Specific description of the problem : Two at a time script Duplication : & ...

  9. Mongodb Basic syntax

    Some time ago, I didn't have much work, so I played mongodb, I learned its basic grammar , And now let's make a simple summary . 1. I was in win On the platform , It's troublesome to start it up , So I simply made the startup process a batch file start-up ...

  10. [ Re posting ] Carry out the name change through to the end ,Xeon E3 The series will be renamed Xeon E

    Carry out the name change through to the end ,Xeon E3 The series will be renamed Xeon E Reading guide :    E3 The series was renamed XEON E series entry The meaning of entry level E5 1XXX The sequence was renamed XEON W series workstatio ...