GCD XOR UVA - 12716


題意:《1》   已知a^b=c 等價於a^c=b和b^c=a;


<2>      gcd(a,b)=a^b=c  得出c是a和b的約數,通過枚舉c   和  a 得到b  然後判斷gcd(a,a-c)=a^(a^c)這樣gcd是logn   枚舉是nlogn    總的時間復雜度為   n*logn*logn;


《3》 通過打印一些滿足條件的結果會發現:c=a-b,這樣時間復雜度就變成瞭nlogn (想不到啊。。。。。)


還是看瞭高神的才會的。。。我好菜


#include<iostream>
#include <stdio.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);

}
const int maxn=30000000+10;
int s[maxn];
void Init()
{
for(int i=1;i<=maxn/2;i++)
{
for(int j=i+i;j<=maxn;j+=i)
{
int b=j-i;
if( b==(i^j))
{
s[j]++;
}
}

}
for(int j=2;j<=maxn;j++)
{
s[j]=s[j]+s[j-1];
}
}
int main ()
{
int n;
Init();
cin >> n;
int t;

for(int i=1;i<=n;i++)
{
cin >> t;
printf( "Case %d: %d\n",i,s[t]);
}

return 0;
}

0 個評論

要回覆文章請先登錄註冊