小编Rob*_* Yu的帖子

给出四个正整数 , , 和 ,有没有办法快速找到任何两个整数 和 这样:

• ,和
• ？

什么时候 和 ,有一个封闭的形式 使用二次方程解决这个问题.我们只需找到根源 它会给我们一个合适的 .

什么时候 ,我知道如何解决它 通过注意到曲线 是凸的,所以我们可以二元搜索一个合适的 .

什么时候 ,它可以解决 通过保理 并寻找一对总和到该范围内的值的因子.

然而,当它们都是范围时,我想不出任何可以有效解决这个问题的算法.有一些可能的启发式方法,比如修复两个中的一个(迭代较小的范围等),或立即报告当可以用两个整数求和的最大可能产品时不存在对 小于 等

不幸的是,我无法想出任何能够在一般情况下工作的东西,而不是迭代任何一件事 要么 (可能有一些额外的小因素).是否有一个很好的算法,或一些花哨的数学,提供更快的解决方案？

或者,有没有办法证明迭代很快终止？(在处理了一些角落案件等之后)我对有效对的数量不感兴趣; 找到任何一对都会.如果允许总和的范围足够大,似乎迭代产品并试图找到相应的和趋向于快速找到解决方案.可以有某种证据吗？

我非常感谢任何帮助!

最近,我学习了Mo的查询平方根分解算法,以加快某些问题的解决方案.

为了实现实现,我一直在尝试使用这个想法来解决D.强大的数组(Codeforces上的过去的竞争问题).问题如下:

你有一个数组 整数 .

考虑一个任意的子阵列 .限定 是整数的出现次数 在这个子阵列中.子阵列的功率定义为.的总和 对于所有整数 (请注意,只有正数的术语不是零).

回答 查询.在每个查询中,给出两个整数 和 ,计算功率的.

它拥有:

使用Mo的算法,我编写了代码,可以离线解决这个问题 .我确信使用这种算法和时间复杂度可以解决这个问题,因为我已经检查了其他人接受的代码,他们也使用了类似的算法.

但是,我的代码获得了超出时间限制的判决.

以下是我写的代码:

#include <ios>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>

int sqt;
long long int ans = 0;
long long int arr[200005] = {};
long long int cnt[1000005] = {};
long long int tans[200005] = {};

struct el
{
    int l, r, in; …

我最近想到了以下问题,我很惊讶似乎没有人问过这个问题:

给定一个字符串,存在多少个不同的排列,以模为单位 ？

我知道这个公式 哪里 是字符串的长度,和 是每个角色的数量(考虑大小的字母表 ).所以,字符串toffee会有 不同的排列.

但是这不再适用了 可能真的很大(比如说 ),自计算 会超出long long int的范围,使用BigIntegers会太慢.有没有办法计算这个,比方说, 要么 时间？

如果我预处理了因子 至 ,我的"字符串"以长度数组的形式出现 其中每个元素包含每个字母的计数,是否可以计算它 要么 时间？

将不胜感激任何帮助:)