A - Add and Divide

题意

有两个数a和b，每次可以选择把a除去b（下取整）或者把b加1，问最少操作几次使a等于0。
\(a,b\le10^9\)

题解

显然这个操作次数不会很多，因为哪怕a是\(10^9\)，b是2，最多操作32次肯定够了。

而且注意到第二个操作肯定放在操作的最前面。

于是暴力枚举第二个操作执行几次（\(<32\)）即可。

#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
    char c; int num, f = 1;
    while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
    while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
    return f * num;
}
int ans = 0, a, b;
void work() {
    ans = 0x3f3f3f3f;
    a = read(); b = read();
    int t1, t2, cnt;
    for(int i = 0; i <= 100; i++) {
        if(b + i == 1) continue;
        cnt = 0;
        t1 = a; t2 = b + i;
        while(t1 != 0) {
            t1 /= t2;
            cnt++;
        }
        ans = min(ans, cnt + i);
    }
    printf("%lld\n", ans);
}
signed main()
{
    int Case = read();
    while(Case--) work();
    return 0;
}

View Code

 

B - Replace and Keep Sorted

题意

定义b与a相似当且仅当：
a,b为严格单调递增的等长正数序列，a,b中的每个元素都在\([1,k]\)中，a,b只有一个元素不同。
有q个询问，每次询问与a的一个子段相似的b有多少个。
\(n,q\le 10^5,\)

题解

因为只需要改变一个数，我们判断一下每个数可以变化的范围（大于左边的数小于右边的数）就行了。
但是注意区间两端的数需要特判，因为左端点只要大于0，右端点只要小于k+1即可。

#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
    char c; int num, f = 1;
    while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
    while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
    return f * num;
}
const int N = 2e5 + 1009;
int n, q, k, a[N], b[N];
void work() {
    n = read(); q = read(); k = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    a[0] = 0; a[n + 1] = k + 1;
    for(int i = 1; i <= n; i++) 
        b[i] = a[i + 1] - 1 - (a[i - 1] + 1) + 1 - 1 + b[i - 1];
    //for(int i = 1; i <= n; i++)
    //    cout << b[i] - b[i - 1] << endl;
    for(int i = 1; i <= q; i++) {
        int l = read(), r = read();
        //cout << b[r - 1] - b[l] << endl;
        if(l == r) printf("%lld\n", k - 1);
        else printf("%lld\n", b[r - 1] - b[l] + a[l + 1] - 1 - 1 + k - a[r - 1] - 1);
    }
}
signed main()
{
    int Case = 1;
    while(Case--) work();
    return 0;
}

View Code

 

C - Floor and Mod

题意

定义一对数\((a,b)\)是漂亮的，有\(\lfloor\frac{a}{b}\rfloor == a mod b\)，求\(1\le a \le x, 1 \le b \le y\)中有多少对\((a,b)\)是漂亮的。

\(a,b\le 10^9\)

题解

我们把式子化简下。

枚举这个b，假设枚举到i。

另\(a = i * k + k(k < i)\)，提出k可以得到\(k = \frac{a}{i+1} <b\)

把b除过来得到\(\frac{a}{i^2+i}=0(<1取整)\)，且\(i+1|a\)

显然a只能是\([0,i^2+i-1]\)之间的一个数而且a能被i整除，这样的a有\(\frac{min(i^2+i-1, x)}{i}\)个。

暴力枚举这个i可以发现答案是对的，但是会超时，继续观察，发现i很大的时候，分子全是x。

分子相同的时候统计这个和可以用数论分块解决。

因为\(i^2+i-1 <= x\)的i最多有\(\sqrt{x}\)个，时间是\(O(\sqrt{x})\)的。

而大于的情况用数论分块之后也是\(O(\sqrt{x})\)的，所以总时间就是\(O(\sqrt{x})\)。

#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
    char c; int num, f = 1;
    while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
    while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
    return f * num;
}
int x, y, ans;
void work() {
    int l, r, i; ans = 0;
    x = read(); y = read();
    for(i = 1; i * i + i - 1 <= x && i <= y; i++) {
        int r = i * i + i - 1;
        ans += r / (i + 1);
    }
    //cout << i << endl;
    l = i + 1;
    for( ; l <= y + 1 && l <= x; l = r + 1) {
        r = x / (x / l);
        if(r > y + 1) break;
        ans += x / l * (r - l + 1);
    }
    if(l <= x) {
        r = y + 1;
        ans += x / l * (r - l + 1);
    }
printf(</span><span style="color: #800000;">"</span><span style="color: #800000;">%lld\n</span><span style="color: #800000;">"</span><span style="color: #000000;">, ans);

}

signed main()

{

int Case = read();

while(Case--) work();

return 0;

}

View Code

 

D - Multiples and Power Differences

题意

有一个\(n\times m\)的矩阵\(a\)要求构造一个矩阵\(b\)使得\(b\)中的每个元素都是\(a\)中对应元素的倍数，并且\(b\)矩阵每个元素与上下左右四个元素之间的差的绝对值可以开四次方根。

\(a\)中元素\(1 \le a_{i,j} \le 16\)

题解

（谁能想到C题这么难的数学题之后搞道简单构造题出来）

1到16的最小公倍数是\(720720\)，是小于\(10^6\)的，于是每个位置都可以填\(720720\)，但是相邻两个数要不一样怎么办。

那就\((i+j-1) mod 2==0\)的位置填\(720720\)，下一个位置是\(x\)就减去\(x^4\)就行了。

（还是要吐槽一句居然比C简单不少）

#include <bits/stdc++.h>
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
    char c; int num, f = 1;
    while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
    while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
    return f * num;
}
int n, m, a[509][509];
signed main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            a[i][j] = read();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if((i + j - 1) & 1) 
                printf("720720 ");
            else printf("%d ", 720720 - a[i][j] * a[i][j] * a[i][j] * a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

View Code