题解 - 非单一点U367093

· · 个人记录

题目

传送门

正解

单独讨论M边形的情况。

不妨设M边形的M个点分别为P_0,P_1,...,P_{M-1}，且外接圆心为O，半径为R。

定义\angle P_iOP_0=\theta_i，设P_0(R,0)。

则有\theta_i=\frac{2\pi i}{M}。

那么我们可以求出

P_i(x_i,y_i) x_i=R\cos\theta_i, y_i=R\sin\theta_i.

那么我们回到原题。

由于非单一点的第二个条件，我们得知它在圆O上。

不妨设N边形（N=n+1）的第i个点与K边形的第j个点重合。

那么我们有：

\theta_i=\theta_j+2k\pi \frac{2\pi i}{N}=\frac{2\pi j}{K}+2k\pi,1\leq j<K<N,i < N \frac{i}{N}=\frac{j}{K}+k \because 0\leq\frac{i}{N}<1,0\leq\frac{j}{K}<1 \therefore k=0 \therefore jN=iK,i=j\frac{N}{K}

例如，当n=9时，N=n+1=10，符合的结果有：

i=0,choose\ j=0 i=1,No\ Way i=2,choose\ j=1,K=5 i=3,No\ Way i=4,choose\ j=2,K=5 i=5,choose\ j=2,K=4 i=6,choose\ j=3,K=5 i=7,No\ Way i=8,choose\ j=4,K=5 i=9,No\ Way

样例答案为6。

假设N=\beta_1^{\alpha_1}\beta_2^{\alpha_2}...\beta_n^{\alpha_n},\beta_i<\beta_j\ when\ i\leq j,且\beta_i为质数。

显然i=pM，且M=\beta_i\beta_j...（\beta_i可能与\beta_j,...相等）

则有j=p,K=\frac{N}{M}。

显然K<N，那么只需得p<\frac NM。

那么我们就能发现非单一点的数量L'实质上是所有小于N且不与N互质的数字的数量再加一。

统计与N互质的数字可以借助于欧拉函数。 介绍

AC代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = (int)5e6;
int a[N];
inline void read(int &x) {  // 返回类型必须为void，否则竞赛中Linux测评会报错，Windows没事
    x = 0;
    short flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        // 此处如果只用if的话容易在数据不规范时出错，特别是cin和read混用
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);  // 48这个数字恰好往后10个数都可以使用位运算，可以写成二进制证明；位运算能用当然更好
        c = getchar();
    }
    x *= flag;
}
/* 
inline int read()
{
    int X = 0, w = 0; char ch = 0;
    while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
*/ 

inline void write(int x)
{
     if (x < 0) putchar('-'), x = -x;
     if (x > 9) write(x / 10);
     putchar(x % 10 + '0');
}

void phi_table()    //打表，求出1500000中所有的数的欧拉函数值
{
    memset(a,0,sizeof(a));a[1]=1;
    for(register int i=2;i<=N;++i)
        if(!a[i])
        {
            for(register int j=i;j<=N;j+=i)
            {
                if(!a[j])a[j]=j;
                a[j]=a[j]/i*(i-1);
            }
        }
}
int main(){
    int T,n;
    read(T);
    phi_table();
    while (T--) {
        read(n);
        write(n+1-a[n+1]);
        putchar('\n');
    }

    return 0;
}