网站5g空间,万能证件p图,wordpress 云存储,企业建设网站好处Problem - C - Codeforces
这道题其实是一道数学题。
先看第一个变量#xff0c;也就是我们要求的答案k的数量#xff0c;但看k是很好确定它的限制条件的#xff0c;要想均匀分成k份#xff0c;n%k必须为0#xff0c;有了k#xff0c;我们再来看m#xff0c;对于a(1)和…Problem - C - Codeforces
这道题其实是一道数学题。
先看第一个变量也就是我们要求的答案k的数量但看k是很好确定它的限制条件的要想均匀分成k份n%k必须为0有了k我们再来看m对于a(1)和a(k1),要使它们除以m后相同肯定满足一下式子a(1)x1*m1n1a(k1)y1*m1n1对于其它的对应的a也是一样的a(2)x2*m2n2a(k2)y2*m2n2……那么只要知道m1是否等于m2就可以了吧如果m1等于m2就说明m存在在有n1和n2的阻碍下显然算不出m不妨将两者相减a(1)-a(k1)(x1-y1)*m1a(2)-a(k2)(x2-y2)*m2,,这个时候求一个m不就是求两式的最大公因数吗为什么是最大公因数因为题中m有限制m要求大于等于2它们的公因数可能有很多个但是大于2的不一定有所以求一个最大公因数看看是否大于2。那么解法显而易见了枚举k然后求每个子数组对应元素差的最大公因数看它是否大于等于2及不等于1如果是ans。 using i64 long long;
i64 gcd(i64 a, i64 b) {while (b) {i64 temp b;ba%b;a temp;}return std::abs(a);
}
void solve() {int n;std::cin n;std::vectorint a(n);for (int i 0; i n; i) {std::cin a[i];}int ans 0;for (int k 1; k n; k) {if (n % k 0) {int g 0;for (int i k; i n; i) {g gcd(g, a[i] - a[i - k]);}ans (g ! 1);}}std::cout ans \n;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin t;while (t--) {solve();}return 0;
}
