杭电多校第十场 hdu6434 Count 欧拉函数打表 快速打表模板

时间：2021-07-28 16:47:22

Problem I. Count

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 42    Accepted Submission(s): 16

Problem Description
Multiple query, for each n, you need to get
n i-1
∑ ∑ [gcd(i + j, i - j) = 1]
i=1 j=1
 
Input
On the first line, there is a positive integer T, which describe the number of queries. Next there are T lines, each line give a positive integer n, as mentioned above.
T<=1e5, n<=2e7
 
Output
Your output should include T lines, for each line, output the answer for the corre- sponding n.
 
Sample Input
4
978
438
233
666
 
Sample Output
194041
38951
11065
89963
 
Source
 
Recommend
chendu   |   We have carefully selected several similar problems for you:  6437 6436 6435 6434 6433 
 
题意：求下面这个式子的值
n i-1
∑ ∑ [gcd(i + j, i - j) = 1]
i=1 j=1
分析：按照上面那个式子直接暴力打表容易得到上面式子的含义是1-n以内偶数的欧拉函数值加上奇数的欧拉函数值除以2的和（注意要快速打表，运用素数快速打表）
AC代码：
#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <bitset>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#define ls (r<<1)

#define rs (r<<1|1)

#define debug(a) cout << #a << " " << a << endl

using namespace std;

typedef long long ll;

const ll maxn = 2*1e7+10;

const ll mod = 998244353;

const double pi = acos(-1.0);

const double eps = 1e-8;

ll num[maxn], sum[maxn], prim[maxn];

int main() {

    ios::sync_with_stdio(0);

    ll T, n;

    memset(num, 0, sizeof num);

    num[1] = 1;

    ll id = 0;

    for( ll i = 2; i <= maxn-10; i ++ ) {

        if(!num[i]) {

            num[i] = i - 1; prim[id++] = i;

        }

        for( ll j = 0; j < id && prim[j]*i <= maxn-10; j ++ ) {

            if(i % prim[j]) {

                num[i*prim[j]] = num[i] * (prim[j]-1);

            }

            else {

                num[i*prim[j]] = num[i] * prim[j];

                break;

            }

        }

    }

    num[1] = 0;

    sum[1] = 0;

    for( ll i = 2; i <= maxn-10; i ++ ) {

        if( i%2 == 0 ) {

            sum[i] = sum[i-1] + num[i];

        } else {

            sum[i] = sum[i-1] + num[i]/2;

        }

    }

    scanf("%lld",&T);

    while( T -- ) {

        scanf("%lld",&n);

        printf("%lld\n",sum[n]);

    }

    return 0;

}

　　

相关文章