bzoj2818

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2818: Gcd

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

Sample Output

HINT

hint

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

Source

湖北省队互测

题目类型：数论

算法分析：首先枚举[1, 1e7]内的每一个素数c，即令gcd (x, y) = c，然后该子问题求解的是在[1,N]内满足上面关系的有序对(x,y)的数量。上式可以化简为gcd(x/c, y/c) = 1，然后问题转换为在[1, N / c]内满足gcd (x /c, y/c) = 1的有序对数的个数，这里可以枚举所有小于等于y的所有的与其互质的x，可见可以使用Euler函数求解。只不过之后将Euler值维护一个前缀和再加上当x恰好等于y时的个数。注意这里应该同时求解出素数表和Euler函数表，否则会TLE

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 10000000 + 66;

//定义素数判断表和素数表
bool prime[maxn+10];
long long primelist[maxn+10], prime_len;
long long euler[maxn+10], sum[maxn+10];

void GetPrime ()
{
    memset (prime, true, sizeof (prime));
    prime_len = 0;

    for (long long i = 2; i <= maxn; i++)
    {
        if (prime[i])
        {
            primelist[prime_len++] = i;
            euler[i] = i - 1;
        }

        for (long long j = 0; j < prime_len; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
            {
                euler[i*primelist[j]] = euler[i] * primelist[j];
                break;
            }

            else
                euler[i*primelist[j]] = euler[i] * (primelist[j] - 1);
        }
    }
}


long long Solve (long long n)
{
    long long tot = 0;
    for (long long i = 0; i < prime_len && primelist[i] <= n; i++)
        tot += 1 + sum[n/primelist[i]];

return tot;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    GetPrime();
    memset (sum, 0, sizeof (sum));

    long long n;
    scanf ("%lld", &n);

    for (int i = 2; i <= n; i++)
        sum[i] += sum[i-1] + (euler[i] << 1);

    printf ("%lld\n", Solve (n));

return 0;
}

100

101

102

103

104

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 10000000 + 66;

//定义素数判断表和素数表

bool prime[maxn+10];

long long primelist[maxn+10], prime_len;

long long euler[maxn+10], sum[maxn+10];

void GetPrime ()

{

memset (prime, true, sizeof (prime));

prime_len = 0;

for (long long i = 2; i <= maxn; i++)

{

if (prime[i])

{

primelist[prime_len++] = i;

euler[i] = i - 1;

}

for (long long j = 0; j < prime_len; j++)

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

{

euler[i*primelist[j]] = euler[i] * primelist[j];

break;

}

else

euler[i*primelist[j]] = euler[i] * (primelist[j] - 1);

}

long long Solve (long long n)

{

long long tot = 0;

for (long long i = 0; i < prime_len && primelist[i] <= n; i++)

tot += 1 + sum[n/primelist[i]];

return tot;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

GetPrime();

memset (sum, 0, sizeof (sum));

long long n;

scanf ("%lld", &n);

for (int i = 2; i <= n; i++)

sum[i] += sum[i-1] + (euler[i] << 1);

printf ("%lld\n", Solve (n));

return 0;

}

bzoj2705

bzoj3229

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨