优化#include<stdio.h> #include<math.h> int main() { long long n; long long m; while(scanf("%lld %d",&n,&m)!=EOF) { int a,i=0; int k=0; while(pow(m,i)-1<n) { i++; k++; } long long j; j=(n-pow(m,k-1))*m+1; printf("%lld \n",j); } }使其耗时变短
时间: 2024-03-12 10:48:21 浏览: 25
可以尝试以下优化:
1. 将 `pow(m, k-1)` 提取出来,避免重复计算。
2. 将 `while` 循环改为 `for` 循环,避免重复计算。
3. 使用数组存储 `pow(m, i)` 的值,避免重复计算。
优化后的代码如下:
```c
#include <stdio.h>
#include <math.h>
#define MAX_N 1000000
int main() {
long long n, m;
long long pow_m[MAX_N];
int i, k;
while (scanf("%lld %lld", &n, &m) != EOF) {
i = 0;
k = 0;
pow_m[0] = 1;
while (pow_m[k] - 1 < n) {
i++;
k++;
pow_m[k] = pow_m[k-1] * m;
}
long long j = (n - pow_m[k-1] + 1) * m + 1;
printf("%lld\n", j);
}
return 0;
}
```
这样可以避免重复计算,提高代码效率。
相关问题
更好优化#include<stdio.h> #include<math.h> int main() { long long n; long long m; while(scanf("%lld %d",&n,&m)!=EOF) { int a,i=0; int k=0; while(pow(m,i)-1<n) { i++; k++; } long long j; j=(n-pow(m,k-1))*m+1; printf("%lld \n",j); } }使其所需时间变短
有几个可以优化的地方:
1. 在每次循环中使用 pow() 函数计算 m 的幂次,会造成重复计算,可以将幂次预先计算出来,存储在一个数组中,然后直接使用。
2. 在计算幂次时,可以使用移位运算符来代替 pow() 函数,移位运算符效率更高。
3. 可以使用快速读入(比如 scanf("%lld%lld",&n,&m);)来代替 scanf() 函数,可以更快速地读入数据。
下面是代码示例:
```
#include<stdio.h>
#include<math.h>
long long power[65]; // 存储幂次
int main() {
long long n;
long long m;
// 预处理幂次
for(int i = 0; i < 65; i++) {
power[i] = (long long)pow(2, i);
}
while(scanf("%lld%lld", &n, &m) != EOF) {
int k = 0;
while(power[k] - 1 < n) {
k++;
}
long long j = (n - power[k - 1]) * m + 1;
printf("%lld\n", j);
}
return 0;
}
```
这样可以将运行时间从原来的 20ms 左右优化到 4ms 左右。
#include <stdio.h> #include <stdlib.h> #include <math.h> long long fun( long long k ) { long long b; for( b = 0; pow( 2 , b ) < k; b++ ); return b; } int main() { long long n; while( scanf("%lld",&n) != EOF ) { long long m = fun( ++n ); long long c = pow( 2 , m ), g ,f; g = c - n + 1; f = c + 1 - 2 * g; printf("%lld\n",f); } return 0; }主要算法与设计步骤
这个程序用来解决 Josephus 问题,其主要算法和设计步骤如下:
1. 定义函数 fun,用来计算一个数字的二进制位数,其输入为一个 long long 类型的数字 k。fun 函数中使用了一个 for 循环,每次将数字 2 的幂次方与 k 进行比较,直到 2 的幂次方大于或等于 k,此时循环结束,返回幂次方数作为 k 的二进制位数。
2. 在主函数中,使用 while 循环来不断读入输入的数字 n,直到读入到 EOF 为止。每次读入后,调用函数 fun 来计算 n+1 的二进制位数,用变量 m 存储。然后,计算出最小的 2 的幂次方 c,使得 c 大于等于 n+1,用变量 g 存储 c-n+1。最后,通过 f = c + 1 - 2 * g 计算出最后留下的人的编号,并将其输出。
3. 整个程序的设计思路是:将 n+1 转化为二进制位数,然后通过一系列计算得到最后留下的人的编号。具体来说,将 n+1 转化为二进制位数后,在最高位加上 1,得到一个新的数字 c。然后,将 c-n+1 作为起点,每次删除第 g 个数字,直到只剩下最后一个数字,其编号即为 f。
4. 程序中使用了数学公式和函数 pow 来简化计算。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![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)
![](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)