C++程序查找使得其与数组每个元素取模结果都相同的‘k’
在这篇文章中,我们将讨论一个程序,用于查找一个整数‘k’,使得它与给定数组的每个元素取模的结果都相同。
例如,假设我们得到了一个数组,
arr = {12, 22, 32}
那么我们得到k的输出值为1、2、5、10。
以数组中两个值‘x’和‘y’(x>y)为例。那么我们有(y+差值)%k = y%k。求解得到,
difference%k = 0
因此,我们将找到数组中最大元素和最小元素之差的所有约数,然后检查每个约数是否对数组中的每个元素都具有相同的余数。
示例
#include<bits/stdc++.h> using namespace std; int equal_modulus (int arr[], int len) { sort(arr, arr + len); int diff = arr[len-1] - arr[0]; //vector to store all the divisors vector <int> divi; for (int i = 1; i*i <= diff; i++) { if (diff%i == 0) { divi.push_back(i); if (i != diff/i) divi.push_back(diff/i); } } //to check if remainder is equal for every element for (int i = 0; i < divi.size(); i++) { int temp = arr[0]%divi[i]; int j; for (j = 1; j < len; j++) if (arr[j] % divi[i] != temp) break; //to print the values of k if (j == len) cout << divi[i] <<" "; } return 0; } int main() { int arr[] = {12, 22, 32}; int len = sizeof(arr)/sizeof(arr[0]); cout << "The values of K :" << endl; equal_modulus(arr, len); return 0; }
输出
The values of K : 1 2 10 5
广告