POJ-2478 Farey Sequence 题解

题目大意

法理序列Fn是指对于任意整数n( n >= 2)，由不可约的分数a/b（0 < a < b <= n），gcd(a,b) = 1升序排列构成的序列，最开始的几个如下
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

你的任务是计算法理序列Fn中的元素个数。

解题思路

裸的欧拉函数。

欧拉函数：对于一个正整数n，小于n且和n互质的正整数（包括1 ）的个数，记做φ(n) 。

通式：$φ(x)=x\times (1-1/p1)\times (1-1/p2)\times (1-1/p3)\times (1-1/p4)…..(1-1/pn)$,其中$p1,p2,···,pn$为x的所有质因子（不包括1，1不是质数），x是不为0的整数。$φ(1)=1$（唯一和1互质的数就是1本身）。

直接用埃氏筛，枚举到质数时，对于每个他的倍数，乘上$\Large \frac{p_i - 1}{p_i}$即可。

但是每输入一遍就跑一遍会超时，所以可以提前跑一遍最大值，然后前缀和，输出答案即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6 + 5;
int cnt;
long long prime[N], les[N];
bool vis[N];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

void init(ll maxn) {
	cnt = 0;
	for (ll i = 2; i <= maxn; i++) {
		if (!vis[i]) {
			for (ll j = 2; i * j <= maxn; j++) {
				vis[i * j] = 1;
				if (!les[i * j])	les[i * j] = i * j;
				les[i * j] = les[i * j] / i * (i - 1);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	ll n;
	init(N - 5);
	for (int i = 2; i <= N - 5; i++) {
		if(les[i]) les[i] = i - 1 - les[i];
		les[i] += les[i - 1];
	}
	while (cin >> n && n) {
		ll ans = n * (n - 1) / 2;
		ans -= les[n];
		cout << ans << endl;
	}
	return 0;
}