仪仗队 (欧拉函数) HQG_aC
我们可以将图沿对角线切成两个直角三角形
观察可以发现,从第三行开始,第i行中当前直角三角形范围内能观察到的点数等于(i-1)的欧拉函数值
// luogu-judger-enable-o2
#include
using namespace std;
int a[40001],n;
int fact(int n){if(a[n]>=0) return a[n];a[n]=n*n;for(int i=2;i<=n;i++) a[n]-=fact(n/i);return a[n];
}
int main(){cin>>n;for(int i=0;i1;if(n == 1) cout<<0;else cout<1)+2;
}
本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击【内容举报】进行投诉反馈!
