首页 > 其他分享 >Codeforces Round 942 (Div. 2) D2

Codeforces Round 942 (Div. 2) D2

时间:2024-05-08 19:56:05浏览次数:49  
标签:frac gcd 942 times leq Div D2 统计 nm

链接

题目要求用数学一点的形式表达出来就是统计有多少a,b满足

1.\(1\leq a\leq n ,1\leq b\leq m\)
2.\(\exists k \in N^* ,使得b \times gcd(a,b)=k\times (a+ b)\)
首先,把a和b改写,使得\(gcd(a,b)\)消失
\(a=q*d,b=p*d\),则,\(gcd(a,b)=d\)
条件二变为:\(p\times d^2= k\times (q\times d +q\times d)\)
转化为判断,是否存在正整数\(k\),使得\(p\times d= k\times (q +p)\)成立,也就是\(\frac {p\times d} {q+p}= k\)

也就是我们要对每个\(gcd(q,p)=1\)的数对,验证是否存在这样的\(q\times d\),使得\(\frac {p\times d} {q+p}\)为一个整数。
呃,应该说是对每个\(gcd(q,p)=1\)的数对,统计有多少这样的\(q\times d\),使得\(\frac {p\times d} {q+p}\)为一个整数。
但是这还是不好统计。但是有一个很明显的地方,\(gcd(q,p)=1\),那么,\(gcd(q+p,p)\)等于多少呢?

等于1。辗转相除法可以证明。
所以我们需要统计的其实不是\(q\times d\),而是\(d\)。

统计这个的个数,其实就是枚举所有\(gcd(q,p)=1\)的数对,然后用一个算式直接统计对应的d有多少个。这样的统计是不重复的。
枚举所有的q,p看似不可能,是\(O(nm)\)的,但是从上面的式子中,我们可以发现,我们要找的是\(\frac {d} {q+p}\),$pd\leq n \(,而刚刚的式子表示,\)d\geq q+p\(,我们这里取极端的情况,\)p=1\(,则要求变为\)d>q$ ,结合上面的,$pd\leq n \(可以得到,\)q^2\leq n$,对p也是同理。
所以我们只需要枚举所有\(1\leq q \leq \sqrt n,和1\leq p \leq \sqrt m\),然后统计的部分可以用算式,也可以用循环,用循环的复杂度总体就是\(O({nm}^{\frac{1}{2}}\times ln (nm))\),可以通过

标签:frac,gcd,942,times,leq,Div,D2,统计,nm
From: https://www.cnblogs.com/HLZZPawa/p/18180746

相关文章

  • 2024-05-06 vue获取页面元素高度(注意view标签无法获取到高度,请用div)
    要获取元素高度要满足以下条件:1、组件或页面已加载完毕;2、使用ref绑定的是标准的dom先贴获取方法:用ref绑定元素title,然后在mounted使用this.$refs.title.offsetHeight获取。为什么要满足条件1?因为页面没渲染完成是无法获取到元素的。为什么要满足条件2?如果你是使......
  • Codeforces Round 941 (Div. 2) Div 1 cf941 A-D
     A感觉A比较复杂啊,相比较B简单明了。way1只要有相同的一个数,它的数目大于等于k,那么它就可以进行一次操作,接下来可以再摸k-1个数,那么对于无法凑成k个数的数字来说,无论现在它有多少个数(>=1),加上这k-1个数,都能凑成数目>=k。同时,这个操作可以无限循环下去。所以这道题的出题设......
  • P4942 小凯的数字
    题目:P4942小凯的数字小凯的数字题目背景NOIP2018原创模拟题T1NOIPDAY1T1orDAY2T1难度是否发现与NOIP2017DAY1T1有异曲同工之妙题目描述小凯有一天突发奇想,写下了一串数字:$\overline{l(l+1)(l+2)...(r-1)r}$例如:$l=2,r=5$时,数字为:$2345$$l=8,r=12$时数字为:$89......
  • [ARC159F] Good Division
    题意给定一个长度为\(2\timesn\)的数列\(S\)。称一个数列是好的,当且仅当数列中的数可以由每次删除相邻两个不同的数的操作删空。求划分该数列为若干好的字串的方案数。Sol集中注意力。首先显然长度为奇数的序列是没法做的。若序列存在绝对众数,则该序列一定无法删除......
  • G1. Division + LCP (easy version)
    原题链接题解1.二分查找前缀出现次数,用\(kmp\)优化查找算法code#include<bits/stdc++.h>usingnamespacestd;chars[200005];intpre[200005]={0},occ[200005]={0};intn,x;intsolve(intlen){intcnt=1;intit=0;for(intj=len+1;j<=n;j++){......
  • Codeforces Round 943 (Div. 3)
    CodeforcesRound943(Div.3)A.Maximize?题意:给定x,求一个范围在[1,x)的数字y,内使得gcd(x,y)+y最大,输出任意的y思路:数据范围很小,暴力枚举即可voidsolve(){intx;cin>>x;inty=1,ma=0;for(inti=1;i<x;i++){intres=__gc......
  • G2. Division + LCP (hard version)
    G2.Division+LCP(hardversion)Thisisthehardversionoftheproblem.Inthisversion$l\ler$.Youaregivenastring$s$.Forafixed$k$,consideradivisionof$s$intoexactly$k$continuoussubstrings$w_1,\dots,w_k$.Let$f_k$bethemaximal......
  • Codeforces Round 943 (Div. 3)
    无伤但没速通,然后被hack两个题,直接从rk90掉到rk114514+了,我是真他妈的服了。特此纪念A暴力枚举秒了。B二分答案秒了C他妈脑子抽了,差一步完全整解。我们发现只要确定\(a_{\mathbf{1}}\)那么你直接不断加\(x_i\)就能求出\(a_i\),但是直接这么搞过不了样例,观察一下,然后直......
  • D2. Reverse Card (Hard Version)
    D2.ReverseCard(HardVersion)Thetwoversionsaredifferentproblems.Youmaywanttoreadbothversions.Youcanmakehacksonlyifbothversionsaresolved.Youaregiventwopositiveintegers$n$,$m$.Calculatethenumberoforderedpairs$(a,b)$......
  • Educational Codeforces Round 165 (Rated for Div. 2) C. Minimizing the Sum题解
    题意CodeforcesRound809(Div.2)D1.ChoppingCarrots(EasyVersion)给你两个整数\(n(1\len\le3e5),k(0\lek\le10)\),一个数组\(a(1\lea_i\le10^9)\)。你可以进行如下操作最多\(k\)次:选定一个数\(i(1\lei\len)\),让其变为相邻的数(变为\(a_{i-1},a_{i......