((n % i) % j) % n이 C++에서 최대화되는 (i, j) 쌍의 개수

<시간/>

입력으로 숫자 num이 제공됩니다. 목표는 ((num%i)%j)%num이 최대화되고 i와 j가 모두 [1,num] 범위에 있도록 형식 (i,j) 쌍의 수를 찾는 것입니다.

예를 들어 이해하자

입력 - 숫자=4

출력 - ((n % i) % j) % n이 최대화되는 (i, j) 쌍의 개수는 - 3

설명 − 쌍은 다음과 같습니다:(3,2), (3,3), (3,4)

입력 - 숫자=6

출력 - ((n % i) % j) % n이 최대화되는 (i, j) 쌍의 개수는 - 4

설명 − 쌍은 다음과 같습니다:(4,3, (4,4), (4,5), (4,6)

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

우리는 두 가지 접근 방식을 사용하여 이 문제를 해결할 것입니다. 순진한 접근 방식에서는 num을 절반으로 하면 최대 나머지 값을 얻을 수 있습니다. temp=num/2 +1로 설정합니다. 최대 나머지를 total=num%temp로 설정합니다. 0에서 num까지 i,j를 탐색하고 ((num % i) % j) % num ==total이 되도록 i,j를 찾습니다.

입력 num을 정수로 사용합니다.
maximumd_pair(int num) 함수는 num을 받아 ((n % i) % j) % n이 최대화되도록 (i, j) 쌍의 개수를 반환합니다.
초기 카운트를 0으로 합니다.
최대 나머지를 위해 num을 절반으로 줄이십시오. 설정 온도 =((숫자 / 2) + 1).
총계 =num % temp로 최대 나머지를 계산합니다.
쌍(i,j)의 경우. [1,num] 범위의 i 및 j에 대해 두 개의 for 루프를 사용하여 순회합니다.
값((num % i) % j) % num이 합계와 같으면 카운트를 증가시킵니다.
두 for 루프의 끝에서 결과로 count를 반환합니다.

효율적인 접근

최대 나머지 합계 =num % temp 가져오기 여기서 온도는 num/2+1입니다. . 이제 쌍 (i,j)의 경우 최대 나머지를 얻기 위해 i를 num으로 선택해야 합니다. 합계를 최대로 만들기 위해 범위 합계에서 num까지 j를 선택할 수 있습니다. 따라서 쌍의 수는 총 개수가 됩니다. .

num=2인 경우 , 쌍이 (1,1), (1,2), (2,1), (2,2)이므로 4를 반환하고 num-total을 사용하여 계산되지 않습니다.

입력 num을 정수로 사용합니다.
maximumd_pair(int num) 함수는 num을 받아 ((n % i) % j) % n이 최대화되도록 (i, j) 쌍의 개수를 반환합니다.
초기 카운트를 0으로 합니다.
num==2이면 4를 반환합니다.
그렇지 않으면 최대 나머지를 위해 num을 절반으로 줄입니다. 설정 온도 =((숫자 / 2) + 1).
총계 =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