LightOJ - 1078 Integer Divisibility

思路

博弈
先手必勝: 可以走到必敗狀態(tài)
先手必敗: 無論如何也走不到必敗狀態(tài)

該題，模擬一下就知道

若Alice先手的情況，則n%3 == 1 是先手必敗狀態(tài)

若Bob先手的情況，則n%3 == 0 是先手必敗狀態(tài)

代碼

#include<iostream> #include<cstring> #include<algorithm>using namespace std;int main() {int T;scanf("%d", &T);int id = 0;while(T --) {int n;string name;string ans;cin >> n >> name;if(name == "Alice") {if(n % 3 == 1) {ans = "Bob";}elseans = "Alice";}else {if(n % 3 == 0) {ans = "Alice";}elseans = "Bob";}printf("Case %d: %s\n", ++id, ans.c_str());}return 0; }

LightOJ - 1124 Cricket Ranking

思路

和Dev的鮮花類似
唯一不同的是：
鮮花是可以取【0，A[i]】
這里是[l,r]
偏移一下就可以了
[l, r] -> [0, r-l], 同時N也要減去l

代碼

#include<iostream> #include<cstring> #include <algorithm>using namespace std;typedef long long LL;const int N = 20, mod = 100000007; LL A[N]; LL n, m; int down;LL qmi(LL a, LL b, int mod) {LL res = 1;while(b) {if(b & 1)res = (LL)res * a % mod;a = (LL)a * a % mod;b >>= 1;}return res; } LL C(LL a, LL b) {if(a < b)return 0;int up = 1;for (int i = a; i > a - b; i --) {up = (LL)i % mod * up % mod;}return (LL)up * down % mod; }int main() {int T;int id = 0;scanf("%d", &T);while(T --) {scanf("%lld%lld", &n, &m);for (int i = 0; i < n; i ++){LL l, r;scanf("%lld%lld", &l, &r);r -= l;m -= l;A[i] = r;}// 預(yù)處理1/((n-1)!)down = 1;for (int i = 1; i <= n - 1; i ++)down = (LL)i * down % mod;down = qmi(down, mod - 2, mod);LL res = 0;for (int i = 0; i < 1 << n; i ++) {int sign = 1;LL a = m + n - 1, b = n - 1;for (int j = 0; j < n; j ++)if(i >> j & 1) {sign *= -1;a -= A[j] + 1;}res = (res + C(a, b) * sign) % mod;}printf("Case %d: %lld\n", ++id, (res + mod) % mod);}return 0; }

LightOJ - 1144 Ray Gun

思路

${\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)=1]$

莫比烏斯函數(shù)，容斥原理, 整除分塊

代碼

#include<iostream> #include<cstring> #include<algorithm>using namespace std;const int N = 1e6 + 10; int primes[N]; bool st[N]; int cnt; int mu[N]; int sum[N];void moblus() {memset(st, false, sizeof st);mu[1] = 1;cnt = 0;for (int i = 2; i < N; i ++) {if(!st[i]) {primes[cnt++] = i;mu[i] = -1;}for (int j = 0; primes[j] * i < N; j ++){int t = primes[j] * i;st[t] = true;if(i % primes[j] == 0) {mu[t] = 0;break;}mu[t] = mu[i] * -1;}}for (int i = 1; i < N; i ++) {sum[i] = sum[i - 1] + mu[i];} }int main() {moblus();int T;scanf("%d", &T);int id = 0;while(T --) {long long n, m;scanf("%lld%lld", &n, &m);if(n > m)swap(n, m);long long res = 0;for (long long l = 1, r; l <= n; l = r + 1) {r = min(n, min(n / (n / l), m / (m / l)));res += (sum[r] - sum[l - 1]) * (long long)(n / l) * (m / l);}if(n)res++;if(m) res ++;printf("Case %d: %lld\n", ++id, res);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的kuangbin数学训练1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。