题解 | [SDOI2008]仪仗队 #
[SDOI2008]仪仗队
https://www.nowcoder.com/practice/41e95a615ff8414aa39e3993acfeddfc?tpId=388&tqId=11306677&channelPut=tracker1
从原点)
到点)
的这一条射线，如果%5Cne1)
，那么这条射线一定经过并且最先经过点%7D%2C%5Cfrac%7By%7D%7Bgcd(x%2Cy)%7D))
题目的意思相当于从朝这
范围里面发射无数条射线，求每条射线最先经过的点的个数
范围是
当
或者
时，只有一个点即)
或者)
当
时)
也满足条件
然后显然可以用欧拉函数直接得到，但是欧拉函数)
求的是
有多少个与
互质的数，所以结果得先乘以
，然后最后加上
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 4e4 + 10;
int prime[N], idx;
bool st[N];
int oula[N];
void get_prime_oula(){
memset(st, false, sizeof(st));
memset(oula, 0, sizeof(oula));
idx = 0;
oula[1] = 1;
for(int i = 2; i <= N; i ++){
if(!st[i]){
prime[++ idx] = i;
oula[i] = i - 1;
}
for(int j = 1; prime[j] <= N / i; j ++){
st[prime[j] * i] = true;
if(i % prime[j] == 0){
oula[prime[j] * i] = oula[i] * prime[j];
break;
}
else oula[prime[j] * i] = oula[i] * oula[prime[j]];
}
}
}
signed main(){
HelloWorld;
get_prime_oula();
int n; cin >> n;
int ans = 0;
for(int i = 2; i < N; i ++) ans += oula[i];
cout << 2 * ans + 3 << endl;
return 0;
}
