- it技术
- 线性筛欧拉函数模板
const int N
= 1010;
int primes
[N
], cnt
;
bool st
[N
];
int phi
[N
];
void init(int n
)
{
phi
[1] = 1;
for (int i
= 2; i
<= n
; i
++ )
{
if (!st
[i
])
{
primes
[cnt
++ ] = i
;
phi
[i
] = i
- 1;
}
for (int j
= 0; primes
[j
] * i
<= n
; j
++ )
{
st
[i
* primes
[j
]] = true;
if (i
% primes
[j
] == 0)
{
phi
[i
* primes
[j
]] = phi
[i
] * primes
[j
];
break;
}
phi
[i
* primes
[j
]] = phi
[i
] * (primes
[j
] - 1);
}
}
}
