題目描述點擊打開鏈接

解題用到的結論：

? 1. a XOR b=c;則其中任意一個數都可以由另外的兩個數進行相同的運算的得到。

? 2. a-b<=a XOR b。

? 3. 由第二點可以得到a-b<=c，又gcd(a,b)=c且a不可能等于b,故a(=k1c)-b(=k2c)=(k1-k2)c>=c;則a-b=c。

解題思路：

首先對c和a進行枚舉，然后利用a-b=c求得b，再判斷a^b是否等于c。

時間復雜度分析：

因為c是a的因子，對c和a進行枚舉的話就類似于素數篩選，該時間復雜度為O(nlogn)。循環體里面的判斷都是常數階，所以總的時間復雜度為O(nlogn)。

AC代碼實現：

#include <iostream> #include <cstring>using namespace std;const int Maxn=3e7; int s[Maxn+10];void Init() {int a,b,c;memset(s,0,sizeof(s));for(c=1;c<=Maxn/2;c++){for(a=2*c;a<=Maxn;a+=c){b=a-c;if((a^b)==c) s[a]++;}}for(int i=2;i<=Maxn;i++)s[i]+=s[i-1]; }int main() {int T;cin>>T;int cnt=0;Init();while(T--){int n;cin>>n;cout<<"Case "<<++cnt<<": ";cout<<s[n]<<endl;} }

補充：

若是直接利用題目的表面條件，則同樣對c和a進行枚舉，只是里面的就是利用b=a^c求得b，再判斷gcd(a,b)==c，因為歐幾里得算法的時間復雜度為log n；所以總的時間復雜度就是n*log n*log n。因此肯定會超時。

? ? ? ? ??

?

總結

以上是生活随笔為你收集整理的UVA_12716的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。