网站建设汇报,品牌营销策划书,wordpress ipc主题,会员登录wordpress题目链接#xff1a;hdu 4961 Boring Sum 题目大意#xff1a;给定ai数组; 构造bi, kmax(j|0ji,aj%ai0), biak;构造ci, kmin(j|ij≤n,aj%ai0), ciak; 求∑i1nbi∗ci解题思路#xff1a;由于ai≤105,所以预先处理好每一个数的因子#xff0c;然后在处理bi#… 题目链接hdu 4961 Boring Sum 题目大意给定ai数组; 构造bi, kmax(j|0ji,aj%ai0), biak;构造ci, kmin(j|ij≤n,aj%ai0), ciak; 求∑i1nbi∗ci 解题思路由于ai≤105,所以预先处理好每一个数的因子然后在处理bici数组的时候每次遍历一个数。就将其全部的因子更新对于bi维护最大值对于ci维护最小值。 #include cstdio
#include cstring
#include vector
#include algorithmusing namespace std;
typedef long long ll;
const int maxn 1e5;
const int INF 0x3f3f3f3f;int n, arr[maxn5], b[maxn5], c[maxn5], v[maxn5];
vectorint g[maxn5];void get_factor (int n) {for (int i 1; i n; i)g[i].clear();for (int i 1; i n; i) {for (int j i; j n; j i)g[j].push_back(i);}
}void init () {memset(v, 0, sizeof(v));for (int i 1; i n; i) {int u arr[i];int k (v[u] 0 ? i :v[u]);b[i] arr[k];for (int j 0; j g[u].size(); j)v[g[u][j]] max(v[g[u][j]], i);}memset(v, INF, sizeof(v));for (int i n; i 1; i--) {int u arr[i];int k (v[u] INF ? i : v[u]);c[i] arr[k];for (int j 0; j g[u].size(); j)v[g[u][j]] min(v[g[u][j]], i);}
}int main () {get_factor(maxn);while (scanf(%d, n) 1 n) {for (int i 1; i n; i)scanf(%d, arr[i]);init();ll ans 0;for (int i 1; i n; i)ans ans b[i] * 1LL * c[i];printf(%I64d\n, ans);}return 0;
} 转载于:https://www.cnblogs.com/lytwajue/p/6715549.html
