蓝桥第十三届JavaC组省赛回顾（A8题，H巧思满分）

​​​​​​​​

这题 分类讨论，代码就不写了（十多个if）

​​它的三块拼接，边数只可能出现4/6/8这三种可能

​​​​

因为小怂比较菜，水平有限，这题没A，有兴趣可以看一下肖佬的题解​​

​​​​​​​​​

 给定任意两数A和B（A

那么它们之间的差值为B-A

​​​​​​​​​假设A，B存在非1的公因子​​​​​​​C

​​​​​​​​​即A%C=0&&B%C=0

​​​​​​​​​可得(B-A)%C=0

​​​​​​​​​那么，是否可得C的最大值为B-A？

​​​​​​​​​因此，当存在(A+k,B+k)的最大因子即为 (B-A)

​​​​​​​​所以，只需要构造(A+k)%(B-A)=0,且k尽可能小(k>0)

​​​​​​​​那么，我们可以求出A%(B-A)后，B-A减去该值，即为A最小增加k个值可以满足下一个模为0的值

​​​​​​​​​当然，还有另一个方案：C=A/(B-A),则k=(C+1)*(B-A)-A;

import java.util.Scanner;

public class GCD {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long a=sc.nextLong();
        long b=sc.nextLong();
        long max=Math.abs(a-b);
        System.out.print(max-(a%max));
    }
}

​​​​​​​​​

 这题先说说思路吧：

一开始我的思路是前缀和+后缀和

​​​​​​​​​因为在满足条件的同时，后面的格子中也要有可以停留的位置才能满足条件

​​​​​​​​​但是在写代码的时候遇到了困难

​​​​​​​​​然后群里人说：二分贪心可以做，又去试了一下，写不出来，因为是一个反复跳

​​​​​​​​​最后我思考出正确方案：前缀和+双指针

​​​​​​​​​我们从0位置开始，因为是来回跳2x次，我们先假设跳跃能力为A

​​​​​​​​​则每次可以跳：1,2...A格

那么前提条件就是：我要跳过去x​​​​​​​​​次，那么这A格是不是要有x个落脚点我才可以每一次跳过去的时候可以选择1--A格跳跃

​​​​​​​​​既然过去是x次，回来x次，那么这些格子是不是总共需要停留2x次

​​​​​​​​​即我需要满足条件：A格内的值和大于等于2x

​​​​​​​​​但是我要进行多次往前跳，所以我们需要让每一次跳完后，后面的A个格子内的值和都>=2x即可

​​​​​​​​​（可能讲的不是很清楚，瞅瞅代码，还不懂评论区回复）​​​​​​​

import java.util.Scanner;

public class 青蛙过河 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long x=sc.nextLong();
        long []arr=new long[n+1];
        for (int i=1;i= 2L *x){
                sum=Math.max(sum,i-l);
                l+=1;
            }
        }
        System.out.println(sum);
    }
}

这题用数论分块（不会分块的小伙伴可以百度一下，挺容易理解的）

我的思路：

先判断哪一部分的因数出现次数相同

比如：n=10

那么6/7/8/9/10这5个因子都只出现1次，而4/5则出现2次，3出现3次，2出现5次，1出现10次

然后用连续自然数平方和公式计算总值，乘出现的次数即可(数值过大，开大数)

但是，如果纯粹从1可是到n，那么结果依旧是O(n),会超时

所以在运算时，我们选择判断到一定值后从前往后计算每个数出现的次数

那么这个值我们一般定为

import java.math.BigInteger;
import java.util.Scanner;

public class 因数平方和 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k= (int) Math.sqrt(n);
        int l=0;
        int r=n;
        long s=0;
        BigInteger a = BigInteger.valueOf(1), b = BigInteger.valueOf(2), c = BigInteger.valueOf(6),d,sum=BigInteger.valueOf(0);
        for (int i=1;i<=k;i++){
            l=n/(i+1);
            BigInteger x = BigInteger.valueOf(r), y = BigInteger.valueOf(l);
            d=BigInteger.valueOf(i);
            x = x.multiply(x.add(a)).multiply(x.multiply(b).add(a)).divide(c);
            y = y.multiply(y.add(a)).multiply(y.multiply(b).add(a)).divide(c);
            x = d.multiply(x.subtract(y)).mod(BigInteger.valueOf(1000000007));
            sum=(sum.add(x)).mod(BigInteger.valueOf(1000000007));
            r=l;
        }
        for (int i=1;i<=l;i++){
            k = n / i;
            s += (k * ((long) i * i)) % 1000000007;
            s %= 1000000007;
        }
        sum=(sum.add(BigInteger.valueOf(s))).mod(BigInteger.valueOf(1000000007));
        System.out.println(sum);
    }
}

 ​

因为小怂比较菜，水平有限，这题没A，有兴趣可以看一下肖佬的题解​​