做动感影集的网站,电子商务网站建设设计方案,品牌推广全案,广东微信网站制作哪家好前缀和的一个神奇算法#xff0c;这道题暴力是遍历前缀和的差#xff0c;也就是遍历所有区间和看他是不是能不能正好除尽k
这道题的技巧是将所有前缀和和k求余 按照求余的结果放在一个数组中 那么余数为0的前缀和a一定满足要求#xff08;[0,a]#xff09; 余数相同的两两… 前缀和的一个神奇算法这道题暴力是遍历前缀和的差也就是遍历所有区间和看他是不是能不能正好除尽k
这道题的技巧是将所有前缀和和k求余 按照求余的结果放在一个数组中 那么余数为0的前缀和a一定满足要求[0,a] 余数相同的两两组合范围相减也符合要求所以有Cn2即 (v[i]*(v[i]-1))/2个
那么就把复杂度为O(n2)的循环遍历前缀和算法降低为复杂度为O(n)的算前缀和余数分类的算法。值得学习。
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int k scan.nextInt();long[] q new long[n1];long[] v new long[k];for(int i 1;i n;i){q[i] scan.nextInt() q[i-1];v[(int)(q[i]%k)];}long ans 0;ans v[0];for(int i 0;i k;i){ans (v[i]*(v[i]-1))/2;}System.out.println(ans);//在此输入您的代码...scan.close();}
}
