题解报告（CDUT暑期集训——第六场）

野性酷女 2023-08-17 16:23 55阅读 0赞

# **题解报告（CDUT暑期集训——第六场）** #

--------------------

## **A - oval-and-rectangle** ##

### [HDU - 6362][] ###

*  **思路：水题 积分一化就出来了**
 *  AC代码

--------------------

## **B - bookshelf** ##

### [HDU - 6363][] ###

*  **思路：根据斐波拉契数列和gcd的各种性质 得到ans与gcd的关系 然后对约数使用容斥原理 还要用欧拉降幂防止数据溢出** 
 *  AC代码

--------------------

#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> #include<set> #include<string> #include<sstream> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow_mod(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } int gcd(int a, int b){ return b ? gcd(b, a % b) : a; } int lcm(int a, int b){ return a * 1ll / gcd(a, b) * b; } const int mod = 1e9 + 7; const int N = 1e6 + 10; int tot; int primes[N], mu[N]; bool vis[N]; void Mobius(){ memset(vis, false, sizeof(vis)); mu[1] = 1; tot = 0; for (int i = 2; i < N; i ++ ){ if (!vis[i]){ primes[tot ++] = i; mu[i] = -1; } for (int j = 0; j < tot && i * primes[j] < N; j ++ ){ vis[i * primes[j]] = true; if (i % primes[j] == 0){ mu[i * primes[j]] = 0; break; } else mu[i * primes[j]] = -mu[i]; } } } ll fib[N], fact[N << 1], inv[N << 1], inv_f[N << 1]; ll get_inv(ll n){ return Pow_mod(n, mod - 2, mod); } void init(){ Mobius(); fib[0] = 0, fib[1] = 1; for (int i = 2; i < N; i ++ ) fib[i] = (fib[i - 1] + fib[i - 2]) % (mod - 1); fact[0] = 1; // ÀÛ³Ë for (int i = 1; i < N << 1; i ++ ) fact[i] = (i * fact[i - 1]) % mod; inv[1] = 1; // ÄæÔª for (int i = 2; i < N << 1; i ++ ) inv[i] = ((mod - mod / i) * inv[mod % i]) % mod; inv_f[0] = 1; // ÀÛ³ËÄæÔª for (int i = 1; i < N << 1; i ++ ) inv_f[i] = (inv_f[i - 1] * inv[i]) % mod; } ll C(ll n, ll m){ return fact[n] * inv_f[m] % mod * inv_f[n - m] % mod; } int t, n, k; ll ans, tmp; int main(){ init(); scanf("%d", &t); while (t -- ){ scanf("%d%d", &n, &k); ans = 0; for (int i = 1; i <= n; i ++ ){ if (n % i) continue; tmp = 0; for (int j = i; j <= n; j += i){ if (n % j) continue; tmp = (tmp + 1ll * mu[j / i] * C(n / j + k - 1, k - 1) % mod + mod) % mod; } ans = (ans + tmp * (Pow_mod(2ll, fib[i], mod) - 1 + mod) % mod + mod) % mod; } tmp = C(n + k - 1, k - 1); ans = ans * Pow_mod(tmp, mod - 2, mod) % mod; printf("%lld\n", ans); } return 0; }

## **L - Pinball** ##

### [HDU - 6373][] ###

*  **思路：水题 图一画就出来了（最开始想错了样例都过不去卡了半小时**
 *  AC代码

--------------------

转载于:https://www.cnblogs.com/Misuchii/p/11276228.html

[HDU - 6362]: http://acm.hdu.edu.cn/showproblem.php?pid=6362
[HDU - 6363]: http://acm.hdu.edu.cn/showproblem.php?pid=6363
[HDU - 6373]: http://acm.hdu.edu.cn/showproblem.php?pid=6373