首页 > 其他分享 >CF338D GCD Table-题解(excrt)

CF338D GCD Table-题解(excrt)

时间:2023-05-05 20:14:02浏览次数:37  
标签:return gcd 题解 ll excrt quad Table mod equiv

CF338D GCD Table

个人评价:还好

算法

扩展CRT

题面

给了一张\(n\times m\)的矩阵,第i行j列的权值是gcd(i,j),现在有一个长度为k的序列A,问是否存在(i,j)使得\(gcd(i,j+l-1)=a_l(1\leq l\leq k)\)

问题分析

我们将对应行设为x,对应列设为y,那么就有如下同余方程组

\(x\equiv (y+l-1)(mod\quad a[l])\)

但还是感觉不行,找一下y和a的规律,好像没有办法搞

我们对于x和y分别分析:

1.对于x来说:

序列a中的每一个元素都是x的因数,显然有\(x=lcm(a[i])\times k\),其中\(k\)不一定是一个质数

2.对于y来说:

我们将同余方程拆开,那么可以得到如下方程组

\(y\equiv 0(mod\quad a[1]),y+1\equiv 1(mod\quad a[2])……\)

稍微结合一下下就是

\[\left\{ \begin{aligned} y\equiv 0(mod\quad a[1]) \\ y\equiv -1(mod\quad a[2]) \\ y\equiv -2(mod\quad a[3]) \\ y\equiv -3(mod\quad a[4]) \\ y\equiv -(k-1)(mod\quad a[k]) \\ \end{aligned} \right. \]

然后我们就可以y给解出来,同理,只要判断一下下x是否有解就行了

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll M=1e4+10;
ll n,m,k,a[M];
struct equations{
	ll p,r;
}b[M];
ll qmul(ll x,ll y,ll mod){ 
    return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;
}
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	ll r=exgcd(b,a%b,x,y),tmp;
	tmp=x;x=y;y=tmp-(a/b)*y;
	return r;
}
ll inv(ll a,ll b){
	ll x,y;
	x=0,y=0;
	exgcd(a,b,x,y);
	while(x<0)x+=b;
	return x;
}
void init(){
	 for(ll i=1;i<=k;i++){
	 	b[i].p=a[i];
	 	b[i].r=1-i;
	 	b[i].r=(b[i].r+b[i].p)%b[i].p;
	 }
}
ll solve(){//这个excrt卡了我半年……
	int fg=1;
	for(ll i=2;i<=k;i++){
		ll mul1=b[i-1].p,mul2=b[i].p;
		ll r1=b[i-1].r,r2=b[i].r;
		ll GCD=gcd(mul1,mul2);
		if((r2-r1)%GCD!=0){
			printf("NO");
			exit(0);
		}
		b[i].p=(mul1*mul2)/GCD;
		b[i].r=qmul(qmul(inv(mul1/GCD,mul2/GCD),(r2-r1)/GCD,mul2/GCD),mul1,b[i].p)+r1;
        b[i].r=(b[i].r%b[i].p+b[i].p)%b[i].p;
	}
	if(fg==0||k==1)return -1;
	if(b[k].r==0)return b[k].p;
	return b[k].r;
}
int main(){
	ll lcm=1;
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i=1;i<=k;i++){	
		scanf("%lld",&a[i]);
		lcm=lcm/gcd(lcm,a[i])*a[i];
		if(lcm>n){//注意越界判断
			printf("NO");
			return 0;
		}
	}
	init();
	ll y=solve();
	if(y+k-1>m){//同样是越界判断
		printf("NO");
		return 0;
	}
	for(int i=1;i<=k;i++){
		if(gcd(lcm,y+i-1)!=a[i]){//对于x的分析可得
			printf("NO");
			return 0;
		}
	}
	printf("YES");
	return 0;
}

总结

我们在一些数论的题目当中试着将一些公式带数据yy套进去,看一下能不能套对,反正数论的基础公式就那几个

标签:return,gcd,题解,ll,excrt,quad,Table,mod,equiv
From: https://www.cnblogs.com/Zhangrx-/p/17375215.html

相关文章

  • P8446 虹色的北斗七星 题解
    传送门前言:很久之前做的一道题目了,当时并没有想出来怎么做,随便猜了个结论交上去发现过了。(好像还是第一道自己做出来的绿)简要题意:你有一个长度为\(n\)的序列\(a\),一个区间\([l,r]\)的价值定义为当前区间的极差减去区间长度,求出最大的价值。\(Solution\):看了看题解,发现......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\),表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\),第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\),表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\),第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • CF1260E Tournament 题解
    妙妙题,但是感觉评不到紫。题目链接。题意luogu题意。有\(n\)个人,贿赂第\(i\)个人的代价为\(a_i\)。这些人中,贿赂代价为\(-1\)的是你的朋友。现在,你可以两两配对,使得编号小的被淘汰,但是,如果你贿赂了编号大的,那么编号大的被淘汰,而编号小的留下。问:使得你朋友夺得冠军的......
  • How Many Tables
    HowManyTablesTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):16865AcceptedSubmission(s):8270ProblemDescriptionTodayisIgnatius'birthday.Heinvitesalotoffriends.Nowit'sd......
  • elementUi+table实现表格数据滚动
    elementUi+table实现表格数据滚动引用vue和elementUICDN//引用elementUICDN<scriptsrc="https://unpkg.com/vue@2/dist/vue.js"></script><!--importJavaScript--><scriptsrc="https://unpkg.com/element-ui/lib/index.js"></......
  • django迁移数据库错误问题解决
    删除所有的pyc文件,迁移文件然后重新运行python3manage.pymakemigrationsdjango.db.utils.InternalError:(1060,"Duplicatecolumnname'addr_id'")运行python3manage.pymigrate--fake然后重新运行python3manage.pymigrate成功!......
  • DataTable添加数据
       在ASP.NET中添加数据到DataTable可以使用以下步骤: 1.创建DataTable对象: DataTabledt=newDataTable(); 2.添加列名: dt.Columns.Add("列名1");dt.Columns.Add("列名2");dt.Columns.Add("列名3"); 3.添加行数据: DataRowrow1=dt.NewRow();ro......
  • ABC269F 题解
    前言题目传送门!更好的阅读体验?题解区的方法思维难度都过大(?),提供一种极其容易的方法。思路题目就是求\(\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}\)。所以很容易想到先算\(\sum\limits_{j=y_1}^{y_2}a_{i,j}\)。这个并不困难:如果\(i\)是奇数,那一行应......
  • LeetCode 27. 移除元素 题解
    题目链接:LeetCode27.移除元素本题大意是要对一个数组进行原地删除数值等于val的元素。双指针算法:通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。快指针(p指针):寻找新数组的元素,新数组就是不含有目标元素的数组慢指针(q指针):指向更新新数组下标的位置当......