首页 > 其他分享 >CF1736B 1200 *

CF1736B 1200 *

时间:2023-03-15 15:24:08浏览次数:36  
标签:int CF1736B long 1200 因子 倍数 公因数

题意

解析

解析:每个a[i]是由b[i]和b[i+1]取最大公因数得出,所以对于每个b[j]来说应该既是a[j]的倍数,又是a[j-1]的倍数。现实在取的时候,可以取b[j] = lcm(a[j-1],a[j])。然后再对每个b[j]检查gcd(b[j],b[j+1])是否真的等于a[j]。
我们这样取保证了b[j]是a[j-1]和a[j]倍数。但不一定b[j]和b[j+1]的最大公因数是a[j],因为有可能b[j]和b[j+1]多出了一个公共因子k,这样此时b[j]和b[j+1]的最大公因子就是k * a[j]了。所以要再检查一下。
这也是为什么我们取的时候取最小公倍数,这可以让其他因子尽可能的少。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10,M = 1e6 + 10;
int t,n,m,a[N],b[N],s[N],l;

bool check(){
    for(int i=1;i<=n;i++){
        if(__gcd(b[i],b[i+1]) != a[i]) return false;
    }
    return true;
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        a[0] = 1;
        a[n+1] = 1;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n+1;i++){
            b[i] = a[i] * a[i-1] / __gcd(a[i],a[i-1]);
        }
        if(check()) puts("YES");
        else puts("NO");
    }
    return 0;
}

标签:int,CF1736B,long,1200,因子,倍数,公因数
From: https://www.cnblogs.com/dtdbm/p/17218672.html

相关文章

  • RS485 MODBUS转PROFINET网关案例 | 超声波明渠流量计接入到PLC1200 PROFINE
    本案例介绍的是用北京小疆智控(北京)技术有限公司生产的GW-PN5003型RS485转PROFINET网关将超声波明渠流量计接入西门子PLC1200PROFINET网络的使用方法:  1、首先创建新......
  • CF522A 1200 *
    题意Polycarp在他的微博上发布了一张有趣的照片。他的很多朋友就开始在微博上转发这张图片,这个事情可以被一个字符串描述:name1repostedname2,意思是说name1这个人转发了n......
  • CF729B 1200
    题意解析我写的朴素的二维前缀和,这样比较麻烦可以这样,f1[i][j]代表当前行第一个到第j个的前缀和f1[i][j]=f1[i][j-1]+a[i][j]f2[i][j]代表当前列第一个到第i个的前......
  • CF1200E Compress Words
    洛谷题目传送门分析模拟过程是先是前两个单词合并,合并之后的句子再接着和第三个单词合并这样子所以过程中肯定是要开个\(ans\)串不断去进行合并预处理和答案累加合并......
  • CF489B 1200 *
    题意解析如果对于一个a数列中的一个最小的数a[x],它可能和多个在b数列的数相匹配,显然,我需要先试试b数列中最小的一个b[y],如果可行,那么赶紧配对,再试试a数列中第......
  • CF433B 1200 普及-
    题意解析水题,普及-,没意思代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10,M=1e6+10;lln,m,v[N],sum1[N],sum......
  • CF327A 1200 *
    题意解析纯暴力枚举,先计算总1数。第一维枚举左端点,第二维枚举右端点,第三维从左端点跑到右端点计算当前区间如果原来是1则减1,原来是0则加1。前缀和优化。一个翻转是1-a......
  • S7-1200作为的IO控制器和智能IO设备的应用
    PLC_1是IO控制器,  PLC_2是智能io设备; 情况1:S7-1200智能设备在相同项目下组态;只需要设置智能IO设备即可;        情况2:S7-1200智能设备在......
  • sft1200插件安装|ssr|istore
    之前都是使用代理软件上网,github都得挂(github访问非常玄学)后来买了xbox,发现xbox上有Netflix,所以最终选择软路由,挑来挑去最终咸鱼130收了这个路由器,比r2s便宜还带wifi,主要......
  • 1200V CoolSiC模块IMBG120R140M1H SICFET N-CH 18A
    IMBG120R140M1H模块SICFETN-CH1.2KV18ATO263(IMBG120R140M1HXTMA1)说明:1200VCoolSiC模块是碳化硅(SiC)MOSFET模块,具有较高的效率和系统灵活性。这些模块采用近阈值......