想要最小化我的代码，使其消耗的时间小于1秒.它使用了模幂的概念.正确的输出，但超过了时间限制

Question

以下代码用于计算2^n，其中n等于1<=n<=10^5。所以为了计算这么大的数，我使用了模指数的概念。代码给出了正确的输出，但由于大量的测试用例，它超过了时间限制。我没有办法最小化解决方案，因此它消耗的时间更少。作为"；algo"；函数的调用次数与测试用例的数量一样多。所以我想把"；algo"；main((函数中的函数，使其消耗小于1秒的时间，并提供正确的输出。这里">t"；表示测试用例的数量，其值为1<=t<=10^5。

你方的任何建议都将大有帮助！！

#include<iostream>
#include<math.h>
using namespace std;
int algo(int x, int y){
long m = 1000000007;
if(y == 0){
return 1;
}
int k = algo(x,y/2);
if (y % 2 == 1){
return ((((1ll * k * k) % m) * x) % m);
} else if (y % 2 == 0){
return ((1ll * k * k) % m);
}

}
int main(void)
{
int n, t, k;
cin>>t; //t = number of test cases
for ( k = 0; k < t; k++)
{
cin >> n;  //power of 2 
cout<<"the value after algo is: "<<algo(2,n)<<endl;
}
return 0;
}

Answer 1

您可以使用二进制移位来查找两个的幂

#include <iostream>
using namespace std;
int main()
{
unsigned long long u = 1, w = 2, n = 10, p = 1000000007, r;
//n -> power of two 
while (n != 0)
{
if ((n & 0x1) != 0)
u = (u * w) % p;
if ((n >>= 1) != 0)
w = (w * w) % p;
}
r = (unsigned long)u;
cout << r;
return 0;
}

Answer 2

这是我经常用来计算的函数
任何整数X的幂为Y的模M

计算(X^Y(mod M的C++函数

int power(int x, int y, const int mod = 1e9+7)
{
int result = 1;
x = x % mod;
if (x == 0)
return 0;
while (y > 0)
{
if (y & 1)
result = ( (result % mod) * (x % mod) ) % mod;
y = y >> 1; // y = y / 2
x = ( (x % mod) * (x % mod) ) % mod;
}
return result;
}

• 如果你不想移除Mod
• 该函数的时间复杂度为O(log2(Y))
• 可能会出现流量过大的情况，因此根据需要使用int , long , long long等

Answer 3

好吧，你的变量无法维持边界测试用例，引入了2^10000，1<=n<=10^5.RIP算法

199506311688075838488374216268358508382349683188619245485200894985294388302194663191996403619459789933112942320912427155649134941378111759378593209632395785573004679379452676524655512660598952055008691813115425086084606181046855090748660888090489898984838009253941633257850621568309473902556912388065225096643874441046759871626985453285381616943157756296407628368807607322285350916414761839563814589694638991084096053626782106462142733339403652556564953060314268023349694003359343165145929777327657756061725820314079941981796073782456837622800373028854872519008344658145465055792960111414833921615734588139257095797691192778008269577356744441230620187578363255027283237892707103738028663930314281332414016241956716905740614196543426388012488561473054319925966111796250130992860241708340076059323201612684922884962558413128440615367389514871142563151110897455142031032022931640957546475610405845841566072044962867016515061920631004186422227590867090546064178569519114560550682512504006007519842261898055932371180544788072906395242548339221982707404473162376760846613033778039800311971334936546227005631699374555082417808109832913144035718775247685098572769379264332215993998768866608083688378380276328277227365757274478411229438973381086160742325397481312019760417828196569747589816531258434135959862784130128185406283476649088690521047580882623961985770122407044330058307586903931960460340497315658320867210591330090375282341553974539439771525745529051031094732161075347482574077527398634829849834075693795566386218745694992790165721037013644331358172143117913982229838473344402709641828510050729277483645505786345011008529781238947392869954083434615880704395911895815147791714361969872813145948378320081474982175801138907122825582681743622057747592141765371568772561490290499246102863008153558330813010198767585623434353895540917562340084452661263568648833519463720377293240095624692325435040067802727383775537640672689636241037491410966718557059098100246788801782719259533812824219540283027594084489501467666838969799688624163631337639390345580140763674187771105538422573949911018646821969658165148513049422236994771476306915546821768287620036277722378136533161119681128079266948188720129864366076855163986053460298715575179473852463694469230878942594821700805322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999267873235802311186264429913575817500819983236284615249881088960232244362117377161808635701546848405862232979285387563386556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304381831540732405331903846208403642176370391155506397890007428536721962809034779745332046836879586858023795221862120080748195513179481576244482985184615097048880272747215746881315947504097321150804981904558034168269497871413160632106391511681774304792596709376

别担心，我的朋友，确实有人试图解决这个问题https://www.quora.com/What-is-2-raised-to-the-power-of-50-000，你正在寻找Piyush Michael的答案，这是他的样本代码

#include <stdio.h> 
int main() 
{ 
int ul=16,000; 
int rs=50,000; 
int s=0,carry[ul],i,j,k,ar[ul]; 
ar[0]=2; 
for(i=1;i<ul;i++)ar[i]=0; 
for(j=1;j<rs;j++) 
{for(k=0;k<ul;k++)carry[k]=0; 
for(i=0;i<ul;i++) 
{ar[i]=ar[i]*2+carry[i]; 
if(ar[i]>9) 
{carry[i+1]=ar[i]/10; 
ar[i]=ar[i]%10; 
} 
} 
} 
for(j=ul-1;j>=0;j--)printf("%d",ar[j]); 
for(i=0;i<ul-1;i++)s+=ar[i]; 
printf("nn%d",s); 
}