用c++语言写以下程序:输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。 输入样例:2 10 9输出样例:2^10 mod 9=7
时间: 2024-02-11 08:09:20 浏览: 27
以下是使用C++语言实现的程序:
```cpp
#include <iostream>
using namespace std;
long long power_mod(long long b, long long p, long long k) {
long long res = 1;
while (p) {
if (p & 1) res = (res * b) % k;
b = (b * b) % k;
p >>= 1;
}
return res;
}
int main() {
long long b, p, k;
cin >> b >> p >> k;
cout << b << "^" << p << " mod " << k << "=" << power_mod(b, p, k) << endl;
return 0;
}
```
使用快速幂算法计算b^p mod k的值,时间复杂度为O(log p)。
相关问题
输入b,p,k的值,求b^p mod k的值(即b的p次方除以k的余数)。其中b,p,k*k为32位整数。分治算法c++
以下是使用分治算法求解b^p mod k的C++代码示例:
```cpp
#include <iostream>
using namespace std;
long long powMod(long long b, long long p, long long k) {
if (p == 0) {
return 1 % k;
}
if (p % 2 == 0) {
long long temp = powMod(b, p / 2, k);
return (temp * temp) % k; } else {
long long temp = powMod(b, p - 1, k);
return (b * temp) % k;
}
}
int main() {
long long b, p, k;
cin >> b >> p >> k;
cout << b << "^" << p << " mod " << k << "=" << powMod(b, p, k) << endl;
return 0;
}
```
用c++语言写以下程序:求逆序对的数目
以下是使用归并排序求逆序对数目的 C++ 代码:
```c++
#include <iostream>
using namespace std;
long long merge(int arr[], int temp[], int left, int mid, int right) {
long long count = 0;
int i = left, j = mid, k = left;
while (i <= mid - 1 && j <= right) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else {
temp[k++] = arr[j++];
count += mid - i;
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return count;
}
long long mergeSort(int arr[], int temp[], int left, int right) {
long long count = 0;
if (left < right) {
int mid = (left + right) / 2;
count += mergeSort(arr, temp, left, mid);
count += mergeSort(arr, temp, mid + 1, right);
count += merge(arr, temp, left, mid + 1, right);
}
return count;
}
long long countInversions(int arr[], int n) {
int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter the elements: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
long long inversions = countInversions(arr, n);
cout << "Number of inversions: " << inversions << endl;
return 0;
}
```
输入格式为:第一行输入元素个数 n,第二行输入 n 个元素。输出逆序对的数目。