13届蓝桥杯省赛Java A 组Q1~Q4+Q8

题目链接Q1蓝桥云课裁纸刀Q2蓝桥云课寻找整数洛谷P12364 [蓝桥杯 2022 省 Python B] 寻找整数Q3蓝桥云课求和洛谷P13892 [蓝桥杯 2023 省 C] 求和Q4蓝桥云课GCDQ8蓝桥云课因数平方和算法原理Q1解法找规律时间复杂度O(1)思路很简单周围的4刀是必须裁的我们可以发现无论先横着裁还是先竖着裁结果都是相同的因此我们可以选择先横着裁20行需要裁19刀剩下的22列的每一行需要裁21刀20行就是20×21刀总共需要裁41920×21443刀Q2解法最小公倍数时间复杂度O(n²)其中 n48记x为最终结果那么为了第一个条件x%21因此可以将x初始化为1我们现在要做的就是不断扩大x保证x的余数能够依次满足各个条件x%32x%41x%54……x%4946那么我们要怎么扩大x保证之前已经满足的条件不被破坏呢当x%21时如果我们持续2发现并不会破坏这一规律3%215%217%21因此我们每次遍历的 i 作为步长再往后试试5%32可以5%41可以5%50≠4此时我们选择遍历的 i 作为步长也就是5发现551010%50这就不行了那要怎么做呢其实这个过程的步长实际上是(tempi )的最小公倍数所以上述过程实际上是这样的1%21✔️templcm(1,2)21%3≠21temp33%3≠23temp55%32✔️templcm(2,3)65%41✔️templcm(6,4)125%5≠45temp1717%5≠417temp2929%54✔️templcm(12,5)60……发现了吗这个过程中temp的值始终能够保证之前的余数符合条件因为它是按遍历过的 i 的最小公倍数增长的Q3解法初中数学公式时间复杂度O(1)从1加到n有个固定公式首尾×个数÷2即1n×n÷2代入即可细节int会溢出需要×1L转成longQ4解法最大公约数最大公约数的核心性质对任意两个整数x、y都有gcd(x,y)gcd(x,y-x)那么gcd(ak,bk)gcd(ak,b-a)必然满足(ak)%gcd0(b-a)%gcd0(ak)是个变量而(b-a)却是定量要想同时满足这两个式子就必须满足(ak)是(b-a)的倍数最大公约数就只能是(b-a)(由于最大公约数非负因此加上绝对值|b-a|用mod表示)那么我们仅需算出a还需多少能够达到这个(b-a)即可① a % mod 得到a除以mod的余数r② mod - r 就是让ak成为mod倍数的最小正整数k因此通过mod-a%mod计算出kQ8解法数论分块逆元时间复杂度O(√n)①原定义拆解f(1) 1² f(2) 1² 2² f(3) 1² 3² f(4) 1² 2² 4² f(5) 1² 5² f(6) 1² 2² 3² 6² f(7) 1² 7² f(8) 1² 2² 4² 8² f(9) 1² 3² 9² f(10) 1² 2² 5² 10²g (10) 就是把上面所有的项全部加起来②求和顺序交换核心优化原来的暴力思路是“横着加”先算每个 f (x)再加起来。但加法有交换律和结合律我们可以“竖着加”把同一个 d 的平方项全部归到一起看看每个 d² 在所有 f (x) 里出现了多少次因数 dd² 在哪些 f (x) 里出现出现总次数总贡献 d² × 次数1f (1)~f (10)所有 f (x) 里都有10 次1² × 102f(2)、f(4)、f(6)、f(8)、f(10)5 次2² × 53f(3)、f(6)、f(9)3 次3² × 34f(4)、f(8)2 次4² × 25f(5)、f(10)2 次5² × 26f(6)1 次6² × 17f(7)1 次7² × 18f(8)1 次8² × 19f(9)1 次9² × 110f(10)1 次10² × 1对于固定的 d1~n 中能被 d 整除的 i 的个数是 ⌊n/d⌋n 除以 d 的整数商向下取整每个这样的 i 都会在 f (i) 中贡献一个d²因为f(x)是因数平方和因此公式可以简化为g(n) Σ(d1到n) d² × ⌊n/d⌋这一步把双重循环直接降为单循环是整个算法的基础③平方和公式与模逆元我们需要快速计算区间[L,R]的平方和Σ(dL到R)d² Σ(1到R)d² - Σ(1到L-1)d²数学上的平方和公式Σ(1到m)d² m*(m1)*(2m1)/6因为题目要求对10^97取模模运算中不能直接做除法需要把除法转为乘以除数的模逆元10^97是质数根据费马小定理6 的模逆元INV6 6^(MOD-2) mod MOD计算结果为166666668模逆元的知识参考下面这篇博客Q2第 179 场双周赛Q1~Q3④数论分块整除分块最终优化对于⌊n/d⌋它的值在一段连续的 d 区间内是完全相同的。例如 n10 时d4、5 时⌊10/d⌋都等于 2d6~10 时都等于 1对于当前左端点left满足⌊n/d⌋ ⌊n/left⌋的最大右端点right n/(n/left)整数除法这样我们可以把1~n分成 O (√n) 个块每个块只需要计算一次时间复杂度从 O (n) 降到 O (√n)Java代码Q1import java.util.Scanner; public class Main { public static void main(String[] args) { System.out.println(41920*21); } }Q2import java.util.*; public class Main{ public static void main(String[] args){ int[] nums {1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17, 9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46}; long x1; long temp2;//步长 for(int i2;i49;i){ while(x%i!nums[i-2]) xtemp; templcm(temp,i); } System.out.println(x); } private static long lcm(long a,long b){ return a*b/gcd(a,b); } private static long gcd(long a,long b){ return b0?a:gcd(b,a%b); } }Q3import java.util.Scanner; public class Main { public static void main(String[] args) { System.out.println(20230409L*20230408L/2); } }Q4import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long asc.nextLong(); long bsc.nextLong(); long modMath.abs(b-a); System.out.println(mod-a%mod); sc.close(); } }Q8import java.util.Scanner; public class Main { private static final int MOD1_000_000_007; private static final long INV61_666_666_68; //计算平方和1²2²3²……x² private static long squareSum(long x){ return ((x*(x1)%MOD)*((2*x1)%MOD)%MOD*INV6%MOD); } public static void main(String[] args) { Scanner sc new Scanner(System.in); int nsc.nextInt(); long ret0L; //数论分块的右端点记录当前块的最右位置 long right; for(long left1L;leftn;leftright1){ //记录当前块的右端点 rightn/(n/left); //计算[left,right]区间内所有数的平方和 //×(n/left):当前块内有(n/left)个相同的值 ret(squareSum(right)-squareSum(left-1))*(n/left)%MOD; //由于计算平方和时用到了取模最终结果可能出现负数 ret(retMOD)%MOD; } System.out.println(ret); sc.close(); } }