shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3897人学习

AtCoder思维大提升

6篇文章 750人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 840人学习

全部文章（共3篇）

龙哥的问题来自专栏

这题思路清晰就好了.最大公约数即为因子,我们把n的因子求出来即可,然后根据欧拉的定理即是答案了.我们知道求gcd(1a,n)=i.就等同于gcd(1a/i,n/i)=1.然后就是统计答案了.代码如下: #include <bits/stdc++.h> using namespace st...

欧拉函数

2020-07-04

2 715

最大公约数来自专栏

求GCD(x,y)为素数个数也就是求d*gcd(x',y')个数,其中gcd(x',y')=1.d是质数.我们考虑枚举d.因为0<x,y<=N,那么x',y'<=N/d.题目就变简单了,那么就是枚举每个质因子.然后用前缀统计下欧拉函数. #include <bits/stdc...

欧拉函数数学

2020-07-04

0 598

acwing 201题解来自专栏

代码: #include <bits/stdc++.h> using namespace std; const int N=1005; int prime[N],cnt=0,f[N],sum[N]; bool st[N]; void init() { f[1]=1; f...

欧拉函数

2020-06-13

1 707