数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中找到使 ((n % i) % j) % n 最大化的 (i, j) 对的数量
给定一个数字 num 作为输入。目标是找到 (i,j) 形式的对的数量，使得 ((num%i)%j)%num 最大化，并且 i 和 j 都在 [1,num] 范围内。
让我们通过例子来理解
输入 - num=4
输出 - 使 ((n % i) % j) % n 最大化的 (i, j) 对的数量为 - 3
解释 - 对将是：(3,2), (3,3), (3,4)
输入 - num=6
输出 - 使 ((n % i) % j) % n 最大化的 (i, j) 对的数量为 - 4
解释 - 对将是：(4,3), (4,4), (4,5), (4,6)
下面程序中使用的方案如下
我们将使用两种方案来解决这个问题。在朴素方案中，如果我们有 num 的一半，则可以获得最大的余数。设置 temp=num/2 +1。将最大余数设置为 total=num%temp。遍历 i、j 从 0 到 num，并找到 i、j 使得 ((num % i) % j) % num == total。
将输入 num 作为整数。
函数 maximized_pair(int num) 获取 num 并返回 (i, j) 对的数量，使得 ((n % i) % j) % n 最大化。
将初始计数设置为 0。
将 num 减半以获得最大余数。设置 temp = ((num / 2) + 1)。
计算最大余数为 total = num % temp;
对于对 (i,j)。使用两个 for 循环遍历 i 和 j 在 [1,num] 范围内。
如果值 ((num % i) % j) % num 等于 total，则增加计数。
在两个 for 循环结束时，返回计数作为结果。
高效方案
获取最大余数为 total = num % temp，其中temp 为 num/2+1。现在对于对 (i,j)，我们必须选择 i 为 num 以获得最大余数。我们可以从 total 到 num 的范围内选择 j 以使 total 最大化。因此，对的数量将为num-total。
如果 num=2，则返回 4，因为对将是 (1,1), (1,2), (2,1), (2,2)，并且不会使用 num-total 计算。
将输入 num 作为整数。
函数 maximized_pair(int num) 获取 num 并返回 (i, j) 对的数量，使得 ((n % i) % j) % n 最大化。
将初始计数设置为 0。
如果 num==2，则返回 4。
否则将 num 减半以获得最大余数。设置 temp = ((num / 2) + 1)。
计算最大余数为 total = num % temp;
设置 count=num-total
最后返回计数作为结果。
示例（朴素方案）
#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
int count = 0;
int temp = ((num / 2) + 1);
int total = num % temp;
for (int i = 1; i <= num; i++){
for (int j = 1; j <= num; j++){
int check = ((num % i) % j) % num;
if (check == total){
count++;
}
}
}
return count;
}
int main(){
int num = 10;
cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}输出
如果我们运行以上代码，它将生成以下输出 -
Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6
示例（高效方案）
#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
int count = 0;
if (num == 2){
return 4;
}
else{
int temp = ((num / 2) + 1);
int total = num % temp;
count = num - total;
}
return count;
}
int main(){
int num = 10;
cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}输出
如果我们运行以上代码，它将生成以下输出 -
Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6
87 次查看
