int mi(int p,int c){ int ans=1; for(;c;c>>=1){ if(c&1==1)ans*=p; p*=p; } return ans; }
时间: 2024-05-20 08:13:32 浏览: 8
这是一个快速幂算法的实现,用于求解 $p^c$ 的值,其中 $p$ 和 $c$ 均为正整数。该算法的时间复杂度为 $O(\log c)$,比直接进行 $c$ 次乘法运算更加高效。
具体实现过程如下:
1. 初始化 ans=1。
2. 循环迭代,每次判断 c 是否大于 0,如果 c=0 则跳出循环。
3. 判断 c 的当前二进制位是否为 1,如果是则将 ans 乘上 p。
4. 将 p 自乘一次,表示将底数平方。
5. 将 c 右移一位,相当于将指数除以 2。
6. 返回 ans。
例如,调用 mi(2,5) 函数,其执行过程如下:
1. 初始化 ans=1。
2. 循环迭代,第一次迭代时,c=5>0,继续执行;
3. 判断 c 的当前二进制位是否为 1,5 的二进制为 101,最低位为 1,ans=2;
4. 将 p 自乘一次,p=4;
5. 将 c 右移一位,c=2;
6. 第二次迭代,c=2>0,继续执行;
7. 判断 c 的当前二进制位是否为 1,2 的二进制为 10,最低位为 0,ans=2;
8. 将 p 自乘一次,p=16;
9. 将 c 右移一位,c=1;
10. 第三次迭代,c=1>0,继续执行;
11. 判断 c 的当前二进制位是否为 1,1 的二进制为 1,最低位为 1,ans=32;
12. 将 p 自乘一次,p=256;
13. 将 c 右移一位,c=0;
14. 跳出循环,返回 ans=32。
因此,mi(2,5) 的返回值为 32。
相关问题
请把下面这个程序改成python语言#include<stdio.h> #include<math.h> int fact(int N) { int ans=1; if(N==0){ } else{ for(int i=1;i<=N;i++) { ans*=i; } } return ans; } int DP(int a,int b) { int ans; return ans=fact(a)/fact(a-b); } int main() { int n; scanf("%d",&n); for(int N=2;N<=n;N++){ int P[N],F[N],sum=0,summ=0; double m[N],fenmusum=0; for(int i=1;i<=N;i++) { F[i]=0; P[i]=DP(N,i); for(int k=0;k<=i;k++) { F[i]+=DP(i,k); } sum+=P[i]*(F[i]-1);//mi分母 } for(int i=1;i<=N;i++) { m[i]=(double)(F[i]-1)/(double)sum; } for(int i=1;i<=N;i++) { fenmusum+=(double)pow((double)(F[i]-1),m[i])*(double)P[i]; } double ans=log(sum)/log(fenmusum); printf("|A|=%d D=%f\n",N,ans); } }
以下是将该程序转换成Python语言的代码:
```python
import math
def fact(N):
ans = 1
if N == 0:
pass
else:
for i in range(1, N+1):
ans *= i
return ans
def DP(a, b):
return fact(a) // fact(a-b)
n = int(input())
for N in range(2, n+1):
P, F, sum, summ, fenmusum = [0]*N, [0]*N, 0, 0, 0
m = [0]*N
for i in range(1, N+1):
F[i] = 0
P[i] = DP(N, i)
for k in range(i+1):
F[i] += DP(i, k)
sum += P[i] * (F[i]-1) #mi分母
for i in range(1, N+1):
m[i] = (F[i]-1) / sum
for i in range(1, N+1):
fenmusum += pow(F[i]-1, m[i]) * P[i]
ans = math.log(sum) / math.log(fenmusum)
print("|A|={} D={}".format(N, ans))
```
注意,Python中没有C语言中的for(int i=1;i<=N;i++)这种写法,需要使用range函数来实现。同时,Python中整数除法要使用//,而不能使用/。此外,Python中没有C语言中的变量类型声明,需要在程序运行时自动推断变量类型。最后,Python中的print语句需要用格式化字符串来输出变量。
c++有一堆机器零件(零件个数小于 100),3 个为一组则剩下 2 个,5 个为一组则剩 下 1 个,7 个为一组则剩下 6 个,求这堆零件一共有多少个? 函数原型:int calc(int x[], int len);
这个问题可以用中国剩余定理来解决,和之前的问题一样。
设该零件的数量为 n,则有:
n ≡ 2 (mod 3)
n ≡ 1 (mod 5)
n ≡ 6 (mod 7)
根据中国剩余定理,可以得到:
n ≡ 23 (mod 105)
因此,该零件的数量为 105k + 23,其中 k 为任意整数。
代码实现如下:
```c++
int calc(int x[], int len) {
int a[] = {3, 5, 7};
int b[] = {2, 1, 6};
int M = 1;
for (int i = 0; i < 3; i++) {
M *= a[i];
}
int ans = 0;
for (int i = 0; i < 3; i++) {
int Mi = M / a[i];
ans += b[i] * Mi * inv(Mi, a[i]);
}
return ans % M;
}
int inv(int a, int b) {
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
```
其中,inv 函数是求逆元的函数,可以用扩展欧几里得算法实现。
调用 calc 函数即可得到结果,例如:
```c++
int x[] = {2, 1, 6};
int len = 3;
int n = calc(x, len);
cout << n << endl; // 输出 23
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)