【数学】魔法阵

题目描述

解题思路

神**又考数学

如果要在一个正多边(x)形中画一个正多边形(z)，也就是每两个新顶点之间会间隔（(x - z) / z）个顶点
怎么求z呢：设（y = x / z），每两个新顶点之间会间隔（y - 1）个顶点，那么把x的因数（y）求出来，（z = x / y）

有一个坑点是，找因数时并不是找到 x \sqrt x x ​就可以了，比如说正12边形可以间隔3（y = 4）个点（正3边形）；

多边形至少3条边，所以正12边形不可以间隔5（y = 6）个点

那么因数边界是$x/y>3$

Code

#include <iostream> 
#include <cstdio>using namespace std;int n, t[20010], a[20000], ans, num, sum;void check (int x){//找因数for (int i = 2; 3 * i <= x; i++)if (x % i == 0)a[++num] = i;
}int main(){scanf ("%d", &n);for (int i = 1; i <= n; i++){scanf ("%d", &t[i]);ans += t[i];//假如一个点都不删}check(n);for (int i = 1; i <= num; i++)//枚举因数for (int j = 1; j <= a[i]; j++)//枚举起点，a[i]之后的点画n/a[i]边形只会和之前的多边形重合{sum = 0;for (int k = j; k <= n; k += a[i])sum += t[k];//暴力求和ans = max (ans, sum);}printf ("%d", ans);
}
//本人太菜不太会算时间复杂度，大约是O（(lgn)^3）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！