14届蓝桥杯省赛Java A 组Q4~Q5

题目链接Q4蓝桥云课棋盘洛谷P13879 [蓝桥杯 2023 省 Java A] 棋盘Q5蓝桥云课互质数的个数洛谷P13880 [蓝桥杯 2023 省 Java A] 互质数的个数算法原理Q4解法前缀和差分时间复杂度O(N²M)此题是A.每日一题——2536. 子矩阵元素加 1的变式基本上一模一样下面是不同点2536. 子矩阵元素加 1把区域内数字1此题区域内翻转解决方式%2这样就能保证结果一定是0或1细节数组中可能出现差分时的-1这也算一次翻转因此我们打印时需要取绝对值Q5解法一暴力枚举仅通过10%测试用例时间复杂度O(a²ᵇ)暴力枚举1~aᵇ的每个数判断这个数与aᵇ是否只有1这一个公因子解法二欧拉函数快速幂时间复杂度O(√alog b)欧拉函数φ(n) 1 到 n 中和 n 互质的数的个数作用专门用来 “一秒算出 1~n 里和 n 互质的数有多少个” 的工具完全不用一个个数快速幂把算aᵇ的时间从 “乘 b 次” 降到 “乘 log₂b 次”—— 比如 b1e18log₂b≈60也就是只需要乘 60 次瞬间出结果作用专门用来 “一秒算出 a 的 1e18 次方” 的工具不用一个个乘欧拉函数底层逻辑容斥原理例子例 1n61~6 里和 6 互质的数是 1、5一共 2 个 → φ(6)2例 2n5质数1~5 里和 5 互质的是 1、2、3、4一共 4 个 → φ(5)4例 3n81~8 里和 8 互质的是 1、3、5、7一共 4 个 → φ(8)4比如 n6它的质因数是 2 和 31~6 里和 6 不互质的数肯定是能被 2 或 3 整除的数能被 2 整除的数6/23 个2、4、6能被 3 整除的数6/32 个3、6这里 6 被减了两次所以要加回来 1 个所以和 6 互质的数的个数 总数 6 - 3 - 2 1 2和我们数的一样把这个式子变形一下就能得到欧拉函数的通用公式其中 p₁、p₂...p_k 是 n 的所有不同的质因数代入式子验证结果准确扩展到题目里的 aᵇ这里有个关键性质aᵇ的质因数和 a 的质因数完全一样比如 a122²×3那 a⁷2¹⁴×3⁷质因数还是 2 和 3只是指数变大了质因数没变所以 φ(aᵇ) 的公式可以写成变形可得因此我们只需要先算 φ(a)再乘以 a 的 (b-1) 次方就能得到结果了计算φ(a)步骤①枚举所有质因数就是找公式中的p₁、p₂...p_k优化仅需枚举到√xi × i ≤ x等价于 i ≤ x / i 这样能避免溢出因为如果x有大于√x的因数那对应的另一个因数肯定小于√x枚举到√x就够了对应代码for(int i 2; i x / i; i )②如果当前数 i 是质因数就把x中所有的 i 都除干净保证每个质因数只算一次比如x12i2时x会变成12/2/23避免重复算2对应代码if(x%i0) while(x%i0) x/i;③对应欧拉函数公式为避免小数先 / i 再× ( i - 1)因为ret一定可以被 i 整除对应代码retret/i*(i-1);④如果最后x1说明剩下的x本身是一个质数也是a的质因数比如a15分解后x5这时候要再乘一次对应代码if(x1) retret/x*(x-1);快速幂底层逻辑指数拆成二进制任何一个数都能拆成 2 的幂次方的和比如5 的二进制是 101 → 5 4 1 2² 2⁰那 2⁵ 2⁴⁺¹ 2⁴ × 2¹也就是说我们不用一个个乘 2只要把 2 不断平方遇到二进制位是 1 的时候把当前的结果乘进去就行举个例子步骤当前 b二进制当前 a不断平方结果 ret操作初始510121开始15 是奇数最后一位 121×2¹2乘当前 aa 平方成 4b 右移成 222 是偶数最后一位 02²42不乘a 平方成 16b 右移成 131 是奇数最后一位 1(2²)²162×2⁴32乘当前 aa 平方成 256b 右移成 0结束0-32结果就是 2⁵32Java代码Q4import java.util.*; public class Main{ public static void main(String[] args){ Scanner scnew Scanner(System.in); int nsc.nextInt(),msc.nextInt(); int[][] diffnew int[n1][n1]; for(int i0;im;i){ int x1sc.nextInt()-1,y1sc.nextInt()-1; int x2sc.nextInt()-1,y2sc.nextInt()-1; diff[x1][y1]1; diff[x21][y21]1; diff[x1][y21]-1; diff[x21][y1]-1; } int[][] matnew int[n][n]; for(int i0;in;i){ for(int j0;jn;j){ //计算三个区域的前缀和 int k1(i0?0:mat[i-1][j]); int k2(j0?0:mat[i][j-1]); int k3(i0||j0)?0:mat[i-1][j-1]; mat[i][j](diff[i][j]k1k2-k3)%2; } } for(int i0;in;i){ for(int j0;jn;j){ System.out.print(Math.abs(mat[i][j])); } System.out.println(); } sc.close(); } }Q5import java.util.*; public class Main{ //暴力枚举会超时 private static final int MOD998244353; public static void main(String[] args){ Scanner scnew Scanner(System.in); long asc.nextInt(),bsc.nextInt(); long ret0; for(int i2;iMath.pow(a,b);i) if(check(i,(long)Math.pow(a,b))) ret(ret1)%MOD; System.out.println(ret); sc.close(); } private static boolean check(long x,long t){ for(int i2;ix;i) if(x%i0t%i0) return false; return true; } }import java.util.*; public class Main{ //欧拉函数快速幂 private static final int MOD998244353; public static void main(String[] args){ Scanner scnew Scanner(System.in); long asc.nextLong(),bsc.nextLong(); //特殊情况 if(a1){System.out.println(0);return;} long reta; long xa; for(int i2;ix/i;i){ if(x%i0){ while(x%i0) x/i; retret/i*(i-1); } } //最后x1说明剩下的x本身是一个质数 if(x1) retret/x*(x-1); System.out.println(ret*pow(a,b-1)%MOD); sc.close(); } //快速幂 private static long pow(long a,long b){ long ret1; for(;b0;b1){ if((b1)1) retret*a%MOD; aa*a%MOD; } return ret%MOD; } }