当前位置: 代码迷 >> 综合 >> caioj 1161 欧拉函数3:可见点数
  详细解决方案

caioj 1161 欧拉函数3:可见点数

热度:72   发布时间:2023-09-20 18:51:30.0

(x, y)被看到仅当x与y互质

由此联想到欧拉函数

x=y是1个点,然后把正方形分成两半,一边是φ(n)

所以答案是2*∑φ(n)+1

#include<cstdio>
#include<cctype>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;typedef long long ll;
const int MAXN = 1123;
ll euler[MAXN];void get_euler()
{_for(i, 1, MAXN) euler[i] = i;_for(i, 2, MAXN){if(euler[i] == i)for(int j = i; j <= MAXN; j += i)euler[j] = euler[j] / i * (i - 1);euler[i] += euler[i-1]; }
}void read(ll& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-1') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}int main()
{get_euler();ll n; read(n);_for(i, 1, n){ll x; read(x);printf("%d %lld %lld\n", i, x, 2 * euler[x] + 1);}return 0;
}

 

  相关解决方案