当前位置：首页 > article >正文

CF1780E Josuke and Complete Graph

article 来源：原创 2023/2/5 14:42:59

原题链接

给定 $R(1\leq L \leq R \leq 10^{18}, L \leq 10^{9})$ , 求 $\leq i <j\leq R)$ 有多少不同的 $g c d (i, j)$ .

记 $g = g c d (i, j)$ , 则 $g∈[L,⌊R/2⌋]时g\in [L, \lfloor R/2\rfloor] 时$ , $\in [2L, R]$ , 符合题意.
当 $g < L$ 时, 考虑整除分块.
若 $g∈[i,r]g\in[i,r]$ 时, $⌊L−1g⌋\lfloor {L - 1\over g} \rfloor$ 相同, 记为 $f$ .
则显然有 $\cdot g \leq L - 1$ , 即 $\cdot g < L$ .
还需满足 $\cdot g\geq L$ , 即 $g≥Lf+1g\geq{L\over f + 1}$ , $g≥⌈Lf+1⌉g\geq\lceil {L\over f + 1}\rceil$ ,
$\cdot g\leq R$ , 即 $g≤Rf+2g\leq{R\over f + 2}$ , $g≤⌊Rf+2⌋g\leq\lfloor {R\over f + 2}\rfloor$ .
$r]\cap[\lceil {L\over f + 1}\rceil,\lfloor {R\over f + 2}\rfloor]$ 符合题意.

整除分块：(以下两段代码等价).

for (int i = st; i <= ed; ++i) ans += num / i;

int L = 0; ed = min(ed, num);
for (int i = st; i <= ed; i = L + 1) {L = min(ed, num / (num / i)); ans += (L - i + 1) * (num / i); 
}

代码如下：

#include <bits/stdc++.h>using namespace std;#define ll long long
#define int long longinline ll read() {ll x = 0, f = 0; char ch = getchar();while (!isdigit(ch)) f = ch == '-', ch = getchar();while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();return f ? -x : x;
}void work() {ll L = read(), R = read(); int res = R / 2 - L + 1; if (res < 0) res = 0; int r = 0; for (int i = 1; i < L; i = r + 1) {r = min(L - 1, (L - 1) / ((L - 1) / i)); int f = (L - 1) / i; int st = (L - 1) / (f + 1) + 1, ed = R / (f + 2);res += max(0ll, min(ed, r) - max(st, i) + 1);  
//		printf("[%d, %d], [%d, %d]\n", i, r, st, ed); }printf("%lld\n", res);   
}signed main() {int t = read(); while (t--) work();  return 0;
}

查看全文

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.dgrt.cn/a/391940.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

CF1780E Josuke and Complete Graph

相关文章：

CF1780E Josuke and Complete Graph

DVWA-XSS(DOM)注入-Low-Medium-Hight

从PCB的结构与工艺理解阻焊（Solder mask）与助焊（Paster Mask）

javaScript中的数组及遍历

如何实现两个笔记本电脑间的文件传输

2022 年，写给自己

【第十届“泰迪杯”数据挖掘挑战赛】B题：电力系统负荷预测分析 31页省一等奖论文及代码

PTA甲级-1009 Product of Polynomials c++

字符串模板

Web3 游戏中的创造者经济：从游戏到平台，用户生成内容的挑战

osx 如何用 podman 和 Kubernetes

n个字符串排序(指针数组实现)

vcs makefile脚本学习

如何利用VS Code高效地写Markdown文档

TCP和UDP网络编程

实体商家做抖音运营如何做矩阵？

代码随想录算法训练营第四十三天 | 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

SpringBoot中的拦截器

Java面试技巧——每天一个Tip之引言

容器化的UERANSIM之nr-binder使用