有祥云网站,需要上传视频的网站,互联网站从事登载新闻业务管理暂行规定,中山模板自助建站问题的唯一难点就是如何表示队长能看到的人数#xff1f;如果建系#xff0c;队长所在的点为#xff08;0,0#xff09;分析几组数据就一目了然了#xff0c;如果队长能看到的点为(m,n),那么gcd#xff08;m#xff0c;n#xff09;1即m n 互质或者是#xff08;0,1如果建系队长所在的点为0,0分析几组数据就一目了然了如果队长能看到的点为(m,n),那么gcdmn1即m n 互质或者是0,11,0两点。证明很简单如果gcdmnd 那么(m/d,n/d)必然会挡住点mn所以gcdmn1是必然的。这样问题就划归到2到n-1有多少数互质。由于欧拉函数的意义是小于n的与n互质的数的个数所以知道欧拉函数意义的人都能第一时间想到答案就是tφ2φ3…φn-1 如果点mn可以被看到根据对称性nm也可以被看到再加上(1,1)(由于(1,1)是唯一不具有对称性的点所以分开来考虑)0,11,0三点所以答案 anst*23 如果定义φ11 那么答案就是φ1φ2φ3…φn-11了 #includeiostream #includecstdio #include math.h using namespace std; int prime[20000]{0},t; bool isprime(int k) { for (int i1;it-1;i) { if (k % prime[i]0)return false; } return true; } int euler(int k) { intnow1,e1,i; while(k!1) { for(inow;it-1;i) { now; if(k % prime[i]0)break; } ee*(prime[i]-1);kk/prime[i]; while (k % prime[i]0) { ee*prime[i]; kk/prime[i]; } } returne; } int main() { t2; int m,n,i,ans0; scanf(%d,n); prime[1]2; for (i2;i40000;i) { mi*2-1; if (isprime(m)) { prime[t]m; t; } } for(i1;in-1;i) { anseuler(i); } ansans*21; printf(%d,ans); return 0; } 转载于:https://www.cnblogs.com/philippica/p/4006937.html
