[CodeForces1110C]Meaningless Operations

Upd - 2019 / 2 / 17: 특수 데이터 의 구 해 방식 을 추가 하 였 습 니 다.
제목 링크:http://codeforces.com/problemset/problem/1110/C
제목 의 뜻 을 약술 하 다.
정의 함수 \ (f (a) \) 는:
\[f(a)=\max\limits_{0
주어진 \ \ (a 1, a 2,..., a q \) 개 질문 에 대해 \ (f (a 1), f (a 2),..., f (a q) \ 를 구하 십시오.
해제
먼저 폭력 코드 를 넣 습 니 다:

int f(int a)
{
    int res=-1;
    for(int b=1;b

그리고 화려 하 게 TLE.
이런 문 제 는 일반적으로 규칙 을 찾 는 것 이다. 우 리 는 먼저 시 계 를 친다.

f(  2)=  3;
f(  3)=  1;
f(  4)=  7;
f(  5)=  7;
f(  6)=  7;
f(  7)=  1;
f(  8)= 15;
f(  9)= 15;
f( 10)= 15;
f( 11)= 15;
f( 12)= 15;
f( 13)= 15;
f( 14)= 15;
f( 15)=  5;
f( 16)= 31;
f( 17)= 31;
f( 18)= 31;
f( 19)= 31;
f( 20)= 31;
f( 21)= 31;
f( 22)= 31;
f( 23)= 31;
f( 24)= 31;
f( 25)= 31;
f( 26)= 31;
f( 27)= 31;
f( 28)= 31;
f( 29)= 31;
f( 30)= 31;
f( 31)=  1;
f( 32)= 63;
f( 33)= 63;
f( 34)= 63;
f( 35)= 63;
f( 36)= 63;
f( 37)= 63;
f( 38)= 63;
f( 39)= 63;
f( 40)= 63;
...... ......

우리 의 깜짝 발견: \ (f (2 ^ {k} - 1) \) 가 불규칙 한 것 을 제외 하고 다른 것 은 모두 \ (2 ^ k - 1 \) 와 관련 이 있 는 것 같 습 니 다.
먼저 간단 한 공식 을 내 놓 았 다.
\[f(n)=2^{k+1}-1(2^k<=n<2^{k+1}-1)\]
조금 보편화 하 다
\[f(n)=2^{\left\lfloor log_2n \right\rfloor+1}-1 (ne 2^{t+1}-1,0\le t\le2^{24},t\in \mathbb{Z}^{+})\]
이렇게 해서 우 리 는 일반 데이터 의 계산 공식 적 인 추 도 를 완성 했다.
특수 데 이 터 는?
시계 쳐!!!

    maptable;
    table[1]=-1;
    table[3]=1;
    table[7]=1;
    table[15]=5;
    table[31]=1;
    table[63]=21;
    table[127]=1;
    table[255]=85;
    table[511]=73;
    table[1023]=341;
    table[2047]=89;
    table[4095]=1365;
    table[8191]=1;
    table[16383]=5461;
    table[32767]=4681;
    table[65535]=21845;
    table[131071]=1;
    table[262143]=87381;
    table[524287]=1;
    table[1048575]=349525;
    table[2097151]=299593;
    table[4194303]=1398101;
    table[8388607]=178481;
    table[16777215]=5592405;
    table[33554431]=1082401;

그 러 고 보 니:
\ (f (2 ^ {k} - 1) \) 도 구 할 수 있어!!!
\ (a = 2 ^ {k} - 1 \ \) 일 때:
\[a\& b=b,a\oplus b=a-b\]
\(a=(111...11)_{(2)}\)
\[\therefore \gcd(a\oplus b,a~\& ~b)=\gcd(a-b,b)\]
더 손상 감소 술 에 따라 얻 을 수 있 습 니 다.
\[\gcd(a-b,b)=\gcd(a,b)\]
지금 은 \ (\ max \ limits {0 만 요구 하면 됩 니 다.
요구 하 는 \ (\ gcd (a, b) \) 의 최대 치 는 \ (b (be a) \) 가 \ (a \) 의 최대 인자 라면 분명 합 니 다.main code

#include
using namespace std;

inline int read(){int x=0,f=1;char c=getchar();while(c'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline int log2(int a){return floor(log(a)/log(2));}

inline int Calc(int a)
{
    if(log2(a)!=log2(a+1))//  a   (1<>Q;
    for(int i=1;i<=Q;i++)
        cout<

다음으로 전송:https://www.cnblogs.com/-Wallace-/p/10388639.html