A、B、C、D略

E、小紅與gcd和sum

題意：

在一個數組中，選擇長度為k的子序列，使得\(gcd(a_1 + ... + a_k) * \sum_{i=1}^{k} a_i\)的值最大

思路：

枚舉每一個值(gcd)與其所對應的sum最大值相乘的結果

代碼

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MAXA = 1'000'000;
    vector<int> cnt(MAXA + 1, 0);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        ++cnt[x];
    }

    int64 answer = 0;
    // 枚舉每一個可能的 gcd 值 d
    for (int d = 1; d <= MAXA; ++d) {
        int64 sum = 0;
        // 累加所有 d 的倍數
        for (int m = d; m <= MAXA; m += d) {
            if (cnt[m]) sum += 1LL * m * cnt[m];
        }
        if (sum) answer = max(answer, 1LL * d * sum);
    }

    cout << answer << '\n';
    return 0;
}

F、小紅與天使貓貓醬

題意：

推公式

思路：

經過一系列計算，可得最后要求計算公式：

注意點
①求逆元：

②歐拉降冪：

③代碼中的注釋處

代碼

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
using namespace std;

const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;
const int mod = 998244353;

//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;

ll ksm (ll a, ll b) {
	 ll res = 1;
	 while (b) {
	 	 if (b & 1) res = res * a % mod;
	 	 b >>= 1;
	 	 a = a * a % mod;
	 }
	 return res;
}
void solve() {
	 ll n;
	 cin >> n;
	 ll one = 400 * (ll)(ksm (100, n % (mod - 1)) + mod - 1) % mod * ksm (81, mod - 2) % mod * ksm (99, mod - 2) % mod;//+mod : 防止變成負數
     ll two = 280 * (ll)(ksm (10, n % (mod - 1)) + mod - 1) % mod * ksm (81, mod - 2) % mod * ksm (9, mod - 2) % mod;
     ll three = (49 * (n % mod)) % mod * ksm (81, mod - 2) % mod;//49 * n爆ll
     ll res = (one + two + three) % mod;
     cout << res << "\n";
     
}
int main() {
	 ios::sync_with_stdio (false);
	 cin.tie(NULL);
	 cout.tie(NULL);
	 t = 1;
	 //cin >> t;
	 while (t --) {
	 	 solve();
	 }
	 return 0;
}

CF1035C. A Good Problem

題意：

構造一個字典序最小的序列，滿足For every \(1 \leq i \leq n\), \(l \leq a_i \leq r\). Additionally, \(a_1 \& a_2 \& \ldots \& a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n\)

思路：

①n為奇數時，顯然全填l一定滿足
②n為偶數時，當n=2時，一定不滿足。否則只考慮\(a_{n-1}\)和\(a_n\)兩位(其他位填l，字典序一定最小)，發現當\(a_{n-1}=a_{n}\)時,有\(a_1 \oplus a_2 \oplus \ldots \oplus a_n=0\)，故只用考慮如何構造\(a_n\)，使得\(a_n \& l = 0\)。設x為l最高位1的位置，發現若\(r>=2^{x+1}\)，一定有解。否則一定無解。
另一種判法：

	if (__builtin_clzll(l) == __builtin_clzll(r)) {
		puts("-1");
		return;
	}

builtin_clzll：返回前導0個數

	以下輸出均為2
	
	int x=3;
    cout<<32-__builtin_clz(x)<<endl;
   	
    
    long long x=3;
    cout<<64-__builtin_clzll(x)<<endl;

代碼

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
using namespace std;

const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;

//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;

void print (__int128 x) {
	 if (x < 0) {
	 	 x = -x;
	 	 cout << "-";
	 }
	 if (x > 9) {
	 	 print (x / 10);
	 }
	 cout << (char) (x % 10 + '0');
}
void solve() {
	 ll n, l, r, k;
	 cin >> n >> l >> r >> k;
	 if (n & 1) cout << l << "\n";
	 else {
	 	 if (n == 2) {
	 	 	 cout << "-1" << "\n";
	 	 }else{
	 	 	 int cnt = 0;
	 	 	 for (int i = 63; i >= 0; --i) {
	 	 	 	 if ((l >> i) & 1) {
	 	 	 	 	 cnt = i;
	 	 	 	 	 break;
	 	 	 	 }
	 	 	 }
	 	 	 cnt ++;
	 	 	 __int128 val = (ll)1 << cnt;
	 	 	 if (val > r) {
	 	 	 	 cout << "-1" << "\n";
	 	 	 }else if (k <= n - 2) {
	 	 	 cout << l << "\n";
	 	      }else{
	 	 	 	 print (val);
	 	 	 	 cout << "\n";
	 	 	 }
	 	 }
	 }
}
int main() {
	 ios::sync_with_stdio (false);
	 cin.tie(NULL);
	 cout.tie(NULL);
	 t = 1;
	 cin >> t;
	 while (t --) {
	 	 solve();
	 }
	 return 0;
}