首页 > ACM题库 > HDU-杭电 > HDU 4676-Sum Of Gcd-数论-[解题报告]HOJ
2015
09-17

HDU 4676-Sum Of Gcd-数论-[解题报告]HOJ

Sum Of Gcd

问题描述 :

Given you a sequence of number a1, a2, …, an, which is a permutation of 1…n.
You need to answer some queries, each with the following format:
Give you two numbers L, R, you should calculate sum of gcd(a[i], a[j]) for every L <= i < j <= R.

输入:

First line contains a number T(T <= 10),denote the number of test cases.
Then follow T test cases.
For each test cases,the first line contains a number n(1<=n<= 20000).
The second line contains n number a1,a2,…,an.
The third line contains a number Q(1<=Q<=20000) denoting the number of queries.
Then Q lines follows,each lines contains two integer L,R(1<=L<=R<=n),denote a query.

输出:

First line contains a number T(T <= 10),denote the number of test cases.
Then follow T test cases.
For each test cases,the first line contains a number n(1<=n<= 20000).
The second line contains n number a1,a2,…,an.
The third line contains a number Q(1<=Q<=20000) denoting the number of queries.
Then Q lines follows,each lines contains two integer L,R(1<=L<=R<=n),denote a query.

样例输入:

1
5
3 2 5 4 1
3
1 5
2 4
3 3

样例输出:

Case #1:
11
4
0

静态区间查询,没有更新操作,瞬间就想起来了哪个O(n*sqrt(n))的做法。关键是区间转移的时候不会处理了,只能说数学拙计了……

对于此类问题的时间复杂度分析,详见:http://blog.csdn.net/yang_7_46/article/details/9618637

买一送一,之前一场多校的题目的题解给的是树状数组,其实也可以用这个算法水过,时间也挺快。

http://blog.csdn.net/yang_7_46/article/details/9734635

这道题目的数学分析,等我把整块数论的想明白了总结一下发上来。


#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

#define N 20002
struct node {
    int l, r, b, id;
} q[N];
int n, a[N], m, L, R, c[N], phi[N];
ll sum, ans[N];
vector<int> d[N];
bool cmp(const node &x, const node &y) {
    if (x.b == y.b) return x.r < y.r;
    return x.b < y.b;
}
ll add(int val) {
    ll ret = 0;
    for (int i=0; i<d[val].size(); i++)
        ret += phi[d[val][i]]*(c[d[val][i]]++);
    return ret;
}
ll del(int val) {
    ll ret = 0;
    for (int i=0; i<d[val].size(); i++)
        ret += phi[d[val][i]]*(--c[d[val][i]]);
    return ret;
}
void work(int l, int r, int x) {
    if (x) {
        for (int i=l; i<L; i++) sum += add(a[i]);
        for (int i=R+1; i<=r; i++) sum += add(a[i]);
        for (int i=L; i<l; i++) sum -= del(a[i]);
        for (int i=r+1; i<=R; i++) sum -= del(a[i]);
    } else {
        sum = 0;
        for (int i=l; i<=r; i++) sum += add(a[i]);
    }
    L = l, R = r;
}
int main() {
    for (int i=1; i<N; i++) phi[i] = i;
    for (int i=2; i<N; i++) if (phi[i] == i) {
        for (int j=i; j<N; j+=i) phi[j] = phi[j]/i*(i-1);
    }
    for (int i=1; i<N; i++) for (int j=i; j<N; j+=i) d[j].push_back(i);


    int T;
    scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        memset(c, 0, sizeof(c));
        scanf("%d", &n);
        for (int i=1; i<=n; i++) scanf("%d", &a[i]);
        scanf("%d", &m);
        int block_size = sqrt(n*1.0);
        for (int i=0; i<m; i++) {
            scanf("%d%d", &q[i].l, &q[i].r);
            q[i].b = q[i].l / block_size;
            q[i].id = i;
        }
        sort(q, q+m, cmp);

        for (int i=0; i<m; i++) {
            work(q[i].l, q[i].r, i);
            ans[q[i].id] = sum;
        }
        printf("Case #%d:\n", cas);
        for (int i=0; i<m; i++)
            cout << ans[i] << endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yang_7_46/article/details/9990301