帮我把这个代码减少时间复杂度#include <iostream> using namespace std; long long found(long long n,long long m) { long long answer=1,i,a; for(i=2;i<=n;i++) { if(i>answer+m) { a=(i-answer)/m; if(a>n-i) a=n-i; i+=a; answer+=a*m; } answer=(answer+m-1)%i+1; } printf("%d\n",answer); return 0; } int main() { long long n,m; while(scanf("%lld%lld",&n,&m)!=EOF) { if(n<2) printf("1\n"); else found(n,m); } return 0; }
时间: 2024-03-10 16:43:22 浏览: 38
这段代码是求解约瑟夫问题的,主要的时间复杂度瓶颈在于for循环中的每次迭代都需要进行一次取模运算,而取模运算是比较耗时的。可以采用数学方法优化代码,将时间复杂度从O(nm)降低到O(logn)。
具体的做法是利用数学推导得到递推公式,用这个递推公式直接计算出结果,避免了每次迭代都需要进行一次取模运算的问题。
下面是优化后的代码:
```c++
#include <iostream>
using namespace std;
long long found(long long n, long long m)
{
long long answer = 1;
for (long long i = 2; i <= n; i++)
{
answer = (answer + m - 1) % i + 1;
}
printf("%lld\n", answer);
return 0;
}
int main()
{
long long n, m;
while (scanf("%lld%lld", &n, &m) != EOF)
{
if (n < 2)
printf("1\n");
else
found(n, m);
}
return 0;
}
```
这段代码的时间复杂度为O(logn),可以大大提高程序的运行效率。
相关问题
#include <iostream> #include <string> #include <stack> #include <vector> #include <iomanip> using namespace std; 逐行注释以上代码
这是一段C++的程序代码,使用了几个标准库的头文件。以下是逐行的注释:
```
#include <iostream> // 输入输出流库头文件
#include <string> // 字符串库头文件
#include <stack> // 栈库头文件
#include <vector> // 向量库头文件
#include <iomanip> // 格式控制库头文件
using namespace std; // 命名空间
```
这段程序代码导入了五个标准库的头文件,分别是iostream、string、stack、vector、iomanip,它们分别用于处理输入输出、字符串、栈、向量和格式控制。其中iostream是C++中最常用的输入输出流库,string是用于字符串操作的库,stack是用于栈数据结构的库,vector是用于动态数组的库,iomanip是用于格式化输出的库。
最后一行代码使用了命名空间std,这意味着所有的标准库函数和变量都在std命名空间中。如果不使用using namespace std,则需要在使用标准库函数时加上std::前缀。
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)