新闻api Apache 循环 xamarin arraylist msbuild ios4 bower Validator vue实例 vue图表 android项目实战 android项目实例 css最后一个子元素 mac安装hadoop 安卓小程序源码 cmd查看mysql版本 eclipse显示左边目录 java使用redis python中count python做界面 java类 java编程学习 java数组删除 java获取ip地址 java入门代码 java中string的方法 java怎么输出数组 linux系统安装 python源码 sql综合利用工具 在线pr序列设置 海妖花粉哪里多 backtrack3 网络克隆 big5 u盘系统下载 图片轮播代码 古风头像女动漫 亚索刀光
当前位置: 首页 > 学习教程  > 编程语言

CF701:C Floor and Mod

2021/2/13 17:12:09 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

CF701:C Floor and Mod 题目链接 解题的思路主要是数学推导式的变换。首先我们得知 ⌊ab⌋amodb⌊\frac{a}{b}⌋ a\ mod\ b⌊ba​⌋a mod b 那我们可得 akbka kb kakbk,其中 kamodbk a\ mod\ bka mod b 继续转化为 a(b1)ka (b 1) ka(b1)k&#xf…

CF701:C Floor and Mod

题目链接
解题的思路主要是数学推导式的变换。首先我们得知 ⌊ a b ⌋ = a   m o d   b ⌊\frac{a}{b}⌋ = a\ mod\ b ba=a mod b
那我们可得 a = k b + k a = kb + k a=kb+k,其中 k = a   m o d   b k = a\ mod\ b k=a mod b
继续转化为 a = ( b + 1 ) k a = (b + 1) k a=(b+1)k,因为 k k k 是余数, k < b k<b k<b,那么从这里我们就可得: k < a k < \sqrt a k<a
于是我们就可以考虑是否能通过遍历 k k k O ( 1 ) O(1) O(1) 查找所有符合条件的 a a a b b b

那么首先确定 k k k 的范围: 1 ≤ k < x 1≤k<\sqrt x 1kx ,这里要注意在代码中计算 x \sqrt x x ,若是取下整就要遍历到等于的情况。

那么对每一个可能的 k k k 去计算所有符合条件的情况,那么现在我们要算的是所有符合条件的 a a a b b b,但其实我们可以发现此时只有一个变量,因为此时的 k k k 确定,只要再确定 a a a b b b 其中一个,根据 a = ( b + 1 ) k a = (b + 1) k a=(b+1)k 就能确定另一变量。那么我们现在以 b b b 为变量,用 b b b 列出所有我们需要符合的条件:
k < b k<b k<b
1 ≤ b ≤ y 1≤b≤y 1by
1 ≤ ( b + 1 ) k ≤ x 1≤(b + 1) k≤x 1(b+1)kx 进而有 1 ≤ b ≤ x / k − 1 1≤b≤x/k-1 1bx/k1
也就是说同时满足上述三个条件的 b b b 的个数,就是满足条件的 a a a b b b的个数。
那么我们只要对上述三个条件去求一个交集,就可得 k < b ≤ m i n ( y , x / k − 1 ) k<b≤min(y, x/k-1) k<bmin(y,x/k1),那么这个区间内的元素个数就是 m a x ( 0 , m i n ( y , x / k − 1 ) − k ) max(0, min(y, x / k - 1) - k) max(0,min(y,x/k1)k)。最后对于每个 k k k 去做一个求和就可以了。

代码实现

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        ll x, y, ans = 0;
        scanf("%lld%lld", &x, &y);
        ll lim = sqrt(x);
        for (ll k = 1; k <= lim; ++k) {
            ans += max(0ll, min(y, x / k - 1) - k);
        }
        printf("%lld\n", ans);
    }
}

本文链接: http://www.dtmao.cc/news_show_700086.shtml

附件下载

上一篇:web框架安全分析

下一篇:邻值查找

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?