2021“MINIEYE杯”中国大学生算法设计超级联赛（1）题解

😊 | Powered By HeartFireY | MINIEYE Contest 1 Solution A.Mod, Or and Everything

Problem Description

You are given an integer n n n.

You are required to calculate ( n m o d 1 ) o r ( n m o d 2 ) o r . . . o r ( n m o d ( n − 1 ) ) o r ( n m o d n ) (n mod 1) or (n mod 2) or ... or (n mod (n - 1)) or (n mod n) (nmod1)or(nmod2)or...or(nmod(n−1))or(nmodn).

The “or” operation means “bitwise OR”.

Input

The first line contains an integer T ( 1 ≤ T ≤ 5000 ) T(1≤T≤5000) T(1≤T≤5000)representing the number of test cases.

For each test case, there is an integer n ( 1 ≤ n ≤ 1 0 12 ) n(1≤n≤10^{12}) n(1≤n≤1012)in one line.

Output

For each test case, print the answer in one line.

Solution

😀 算法标签：打表找规律

读完题还是没有思路，遂打表 1 1 1​​~ 100 100 100​​​，找规律，打表程序和数据：

打到 100 100 100​，规律特别明显，遂打到 129 129 129验证，发现规律成立： f ( n ) = ⌈ ( l o g 2 ( n ) ) − 1 ) ⌉ − 1 f(n) = \lceil(log2(n)) - 1) \rceil - 1 f(n)=⌈(log2(n))−1)⌉−1 然后写了一发AC。但是这跟题目描述究竟有何联系呢？可以对任意值 x x x而言：对其从 [ 1 , x ] [1, x] [1,x]取模，那么除去他二进制最高非0位，其模数取遍各位为1的情况(可以打表验证)，那么通过题目的按位取或方式得出的结果所有位全为 1 1 1，正好解释了这个规律。

（其实没必要用快速幂 \doge）

#include 
#define int long long
#define ll long long
using namespace std;

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
  return res;
}

signed main(){
    int t = 0; cin >> t;
    while(t--){
        int n = 0, cnt = 0, ans = 0; cin >> n;
        n -= 1;
        while(n){
            n >>= 1;
            cnt++;
        }
        for(int i = 0; i