?題面

解答

這一題如果不知道數(shù)論結(jié)論的話，做這個(gè)題會(huì)有兩種天壤之別的體驗(yàn)

此題包含以下兩個(gè)數(shù)論知識(shí)

1.? 2^0+2^1+2^2+...+2^(n-1)=2^n-1

2.??較大的數(shù)如果比較小的數(shù)的兩倍大1或者小1，則兩者互質(zhì)

所以答案就是2^n-1/2^(n-1)

標(biāo)程1

我的初次解答

#include <bits/stdc++.h>using namespace std;typedef long long int ll;
#define endl "\n"
#define maxLine 110
#define long long int ll;ll num=20;int main() {cout<<(ll)pow(2,20)-1<<"/"<<(ll)pow(2,19);return 0;
}

但是感覺好像有點(diǎn)慢

下午我么們來用快速冪優(yōu)化一下?

標(biāo)程2

使用快速冪優(yōu)化

#include <bits/stdc++.h>using namespace std;typedef long long int ll;
#define endl "\n"
#define maxLine 110
#define long long int ll;// ll mul(ll a,ll b,ll mod)
// {
//     a %= mod;
//     b %= mod;
//     return (a*b-((ll)((long double)a/mod*b))*mod+mod)%mod;
// }
inline ll ksm(ll a,ll b ){ll res=1;while(b){if (b&1) res*=a;b>>=1;a*=a;}return res;
}
int main() {cout<<(ll)ksm(2,20)-1<<"/"<<(ll)ksm(2,19);return 0;
}

奇怪，優(yōu)化后的代碼空間和時(shí)間居然沒有任何提升。。。?