首页 > 其他分享 >Ai+Bj+Ck=X

Ai+Bj+Ck=X

时间:2023-08-21 11:47:30浏览次数:43  
标签:Ck gcd Ai dfrac long Bj

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

考虑 \(n\) 的范围,枚举 \(i\)。

于是就转换成求解 \(Bj+Ck=X-Ai\)。

这是一个扩展欧几里得的典型应用,可以求 \(Bj+Ck=\gcd(B,C)\) 的一组解。而且左边的式子始终一样,所以只需求解一遍。

首先判断右边是否是 \(\gcd\) 的倍数,如果是的话就就将解扩大 \((X-Ai)\div\gcd\)。

根据 \(ax+by=\gcd(a,b)\) 的所有解的公式:

\(x=x_0-k\dfrac{b}{d},y=y_0+k\dfrac{a}{d}\)(\(k\) 为负亦可,下面将左边的当作加,右边的当作减)。

将最小的 \(x\) 对应的解求出。

然后再根据上面的 \(x\) 变成最小的在范围内的数,然后若 \(y\) 也在范围内,那么计算二者每次递增、递减超出边界的最少次数即可。

注意取模,防止爆 long long

AC

标签:Ck,gcd,Ai,dfrac,long,Bj
From: https://www.cnblogs.com/wscqwq/p/17645601.html

相关文章

  • docker 设置环境变量
    dockerrun-itd--namejf--restart=always--privileged=true-p8080:8080-v/home/yida/apps/jf/logs-8076:/usr/local/tomcat/logs-eMYSQL_SERVICE_HOST=10.143.133.118-eMYSQL_SERVICE_PORT=3306-eMYSQL_SERVICE_USER=root-eMYSQL_SERVICE_PASSWORD=5mLzHsy......
  • 浅谈Angular模板指令:ng-template和ng-container的用法
    本篇文章带大家简单了解一下Angular模板的ng-template和ng-container指令,介绍一下ng-template和ng-container指令使用方法。ng-template指令简介ng-template是一个Angular结构型指令,用来渲染HTML。它永远不会直接显示出来。事实上,在渲染视图之前,Angular会把ng-template......
  • Docker 命令汇总
    容器操作查看正在运行的容器:dockerps查看所有容器(包括停止的容器):docker ps -a启动容器:docker start停止容器:docker stop进入正在运行的容器:docker exec -it /bin/bash导出容器为镜像:docker commit删除容器:docker rm镜像操作查看本地镜像列表:docker images拉取镜像:d......
  • Java-logback.xml配置
    <?xmlversion="1.0"encoding="UTF-8"?><configurationdebug="false"><!--定义日志文件的存储地址勿在LogBack的配置中使用相对路径--><propertyname="LOG_HOME"value="\logs"/><!--控制台输出-......
  • ora.erp61.vip FAILED OVER 或者故障节点vip地址查询不到了
    [root@erp61~]#crsctlstatusres-t--------------------------------------------------------------------------------NAMETARGETSTATESERVERSTATE_DETAILS-------------------------------------------------------......
  • AIGC与软件测试
    一、ChatGPT与AIGC生成式人工智能——AIGC(ArtificialIntelligenceGeneratedContent),是指基于生成对抗网络、大型预训练模型等人工智能的技术方法,通过已有数据的学习和识别,以适当的泛化能力生成相关内容的技术。AIGC技术的核心思想是利用人工智能算法生成具有一定创意和质量的内......
  • webpack学习笔记专题目录
    转载请注明来源:http://www.eword.name/Author:ewordEmail:[email protected]学习笔记专题目录webpack专题目录webpack学习笔记MacBook搭建python开发环境【必须】安装Python【必须】安装pip【必须】virtualenv的安装和使用【推荐】安装PyCharm【推荐】Py......
  • webpack 是什么
    转载请注明来源:http://www.eword.name/Author:ewordEmail:[email protected]是什么Webpack是一个前端资源加载/打包工具。它将根据模块的依赖关系进行静态分析,然后将这些模块按照指定的规则生成对应的静态资源。从图中我们可以看出,Webpack可以将多种静态资源......
  • webpack 五大核心概念
    转载请注明来源:http://www.eword.name/Author:ewordEmail:[email protected]五大核心概念一、Entry入口(Entry)指示Webpack以哪个文件为入口起点开始打包,分析构建内部依赖图。二、Output输出(Output)指示Webpack打包后的资源bundles输出到哪里去,以及如何命名。......
  • webpack学习笔记所使用的版本信息
    学习笔记所使用的版本信息学习笔记用到的npm包版本信息[email protected]@[email protected]@[email protected]@[email protected]@[email protected]@[email protected]......