无锡开发网站建设网站百度排名优化

当前位置： 首页 > news >正文

无锡开发网站建设,网站百度排名优化,建盏茶杯知识,虚拟主机和服务器目录 原题解引申出的编程问题非单一点题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 题解题目正解 原题 已知等边 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0​P1​P2​#xff0c;它的外接圆是 O O O#xff0c;设 O O O的半径是 R R R。同时#xff0c;设 Δ … 目录 原题解引申出的编程问题非单一点题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 题解题目正解 原题 已知等边 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0​P1​P2​它的外接圆是 O O O设 O O O的半径是 R R R。同时设 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0​P1​P2​所经过的所有点的集合是 S 0 S_0 S0​。显然 S 0 S_0 S0​中有无限个元素。 接下来在 O O O上取点 P 3 , P 4 , P 5 P_3,P_4,P_5 P3​,P4​,P5​使得四边形 P 0 P 3 P 4 P 5 P_0P_3P_4P_5 P0​P3​P4​P5​是正四边形。记这个四边形经过的所有点的集合为 S 1 S_1 S1​。 接下来在 O O O上取点 P 6 , P 7 , P 8 , P 9 P_6,P_7,P_8,P_9 P6​,P7​,P8​,P9​使得五边形 P 0 P 6 P 7 P 8 P 9 P_0P_6P_7P_8P_9 P0​P6​P7​P8​P9​是正五边形。记这个五边形的点集为 S 2 S_2 S2​。 中间省略 n − 2 n-2 n−2次操作。 最后在 O O O上取点 δ 1 , δ 2 , δ 3 , … , δ n \delta_1,\delta_2,\delta_3,…,\delta_n δ1​,δ2​,δ3​,…,δn​使得 n 1 n1 n1边形 P 0 δ 1 δ 2 δ 3 … δ n P_0\delta_1\delta_2\delta_3…\delta_n P0​δ1​δ2​δ3​…δn​是正 n 1 n1 n1边形。 记所有 P 0 δ 1 δ 2 δ 3 … δ n P_0\delta_1\delta_2\delta_3…\delta_n P0​δ1​δ2​δ3​…δn​上的非单一点的集合为 W ′ W W′。 非单一点的定义是 对于每一个点 S 0 , S 1 , … , S n − 1 S_0,S1,…,S{n-1} S0​,S1​,…,Sn−1​中任意一个集合包含了它 设这个点的坐标是 x , y x,y x,y则 x , y x,y x,y满足 x 2 y 2 R 2 x^2y^2R^2 x2y2R2
显然 P 0 P_0 P0​是一个非单一点。 记 W ′ W W′中元素的个数为 L ′ L L′。 回答下列问题 1当 n 9 n9 n9时求 L ′ L L′ 2当 n 99 n99 n99时求 L ′ L L′ 3证明或证伪 n n n有无限种取值方法使得 L ′ 1 L1 L′1 4求 2 1.048576 × 1 0 6 2^{1.048576\times 10^6} 21.048576×106边形与 3 3 27 3^{3^{27}} 3327的公共点数。 5证明或证伪并非对于所有的 n 2 2 x n2^{2^x} n22x都存在 L ′ 1 L1 L′1。 解 让我们先单独讨论 M M M边形的情况。 不妨设 M M M边形的 M M M个点分别为 P 0 , P 1 , … , P M − 1 P_0,P1,…,P{M-1} P0​,P1​,…,PM−1​且外接圆心为 O O O半径为 R R R。 定义 ∠ P i O P 0 θ i \angle P_iOP_0\theta_i ∠Pi​OP0​θi​设 P 0 ( R , 0 ) P_0(R,0) P0​(R,0)。 则有 θ i 2 π i M \theta_i\frac{2\pi i}{M} θi​M2πi​。 那么我们可以求出 P i ( x i , y i ) x i R cos ⁡ θ i , y i R sin ⁡ θ i . P_i(x_i,y_i)\ x_iR\cos\theta_i,\ y_iR\sin\theta_i. Pi​(xi​,yi​)xi​Rcosθi​,yi​Rsinθi​. 那么我们回到原题。 由于非单一点的第二个条件我们得知它在圆 O O O上。 不妨设 N N N边形 N n 1 Nn1 Nn1的第 i i i个点与 K K K边形的第 j j j个点重合。 那么我们有 θ i θ j 2 k π 2 π i N 2 π j K 2 k π , 1 ≤ j K N , i N i N j K k ∵ 0 ≤ i N 1 , 0 ≤ j K 1 ∴ k 0 ∴ j N i K , i j N K \theta_i\theta_j2k\pi\ \frac{2\pi i}{N}\frac{2\pi j}{K}2k\pi,1\leq jKN,i N \ \frac{i}{N}\frac{j}{K}k\ \because 0\leq\frac{i}{N}1,0\leq\frac{j}{K}1\ \therefore k0\ \therefore jNiK,ij\frac{N}{K} \ θi​θj​2kπN2πi​K2πj​2kπ,1≤jKN,iNNi​Kj​k∵0≤Ni​1,0≤Kj​1∴k0∴jNiK,ijKN​ 例如当 n 9 n9 n9时 N n 1 10 Nn110 Nn110符合的结果有 i 0 , c h o o s e j 0 i 1 , N o W a y i 2 , c h o o s e j 1 , K 5 i 3 , N o W a y i 4 , c h o o s e j 2 , K 5 i 5 , c h o o s e j 2 , K 4 i 6 , c h o o s e j 3 , K 5 i 7 , N o W a y i 8 , c h o o s e j 4 , K 5 i 9 , N o W a y i0,choose\ j0\ i1,No\ Way\ i2,choose\ j1,K5\ i3,No\ Way\ i4,choose\ j2,K5\ i5,choose\ j2,K4\ i6,choose\ j3,K5\ i7,No\ Way\ i8,choose\ j4,K5\ i9,No\ Way i0,choose j0i1,No Wayi2,choose j1,K5i3,No Wayi4,choose j2,K5i5,choose j2,K4i6,choose j3,K5i7,No Wayi8,choose j4,K5i9,No Way 第一问答案为 6 6 6。 假设 N β 1 α 1 β 2 α 2 … β n α n , β i β j w h e n i ≤ j , N\beta_1^{\alpha_1}\beta_2^{\alpha_2}…\beta_n^{\alpha_n},\beta_i\beta_j\ when\ i\leq j, Nβ1α1​​β2α2​​…βnαn​​,βi​βj​ when i≤j,且 β i \beta_i βi​为质数。 显然 i p M ipM ipM且 M β i β j … M\beta_i\beta_j… Mβi​βj​… β i \beta_i βi​可能与 β j , … \beta_j,… βj​,…相等 则有 j p , K N M jp,K\frac{N}{M} jp,KMN​。 显然 K N KN KN那么只需得 p N M p\frac NM pMN​。 对于 N 100 N100 N100的情况 N 2 2 ⋅ 5 2 2 ⋅ 2 ⋅ 5 ⋅ 5 N2^2·5^22·2·5·5 N22⋅522⋅2⋅5⋅5 i 1 × 2 2 , 2 × 2 4 , … , 49 × 2 98. 1 × 5 5 , 2 × 5 10 , … , 19 × 5 95. i\ 1\times 22,\ 2\times 24,\ …,\ 49\times 298.\ \ 1\times 55,\ 2\times 510,\ …,\ 19\times 595. i1×22,2×24,…,49×298.1×55,2×510,…,19×595. 在这些点中有 9 9 9种重复的情况。因此得到结果为 49 19 − 9 1 60 4919-9160 4919−9160种。还要加上 P 0 P_0 P0​ 总结规律发现实质上就是求 N N N所有的不与它互质且小于它自己的数。注意 N 4 N4 N4因为图里面没有二边形 那么对于每一个质数显然 L ′ L L′只能为 1 1 1。而质数有无限个那么第三问得证。 对于第四问显然这两个数互质没有重复的点。 对于第五问存在许多反例其中一个就是 n 5 n5 n5此时的 N N N不是质数则必定存在除 P 0 P_0 P0​外的非单一点。 引申出的编程问题 Non-Single Points 如下。 非单一点 题目描述 已知等边 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0​P1​P2​它的外接圆是 O O O设 O O O的半径是 R R R。同时设 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0​P1​P2​所经过的所有点的集合是 S 0 S_0 S0​。显然 S 0 S_0 S0​中有无限个元素。 接下来在 O O O上取点 P 3 , P 4 , P 5 P_3,P_4,P_5 P3​,P4​,P5​使得四边形 P 0 P 3 P 4 P 5 P_0P_3P_4P_5 P0​P3​P4​P5​是正四边形。记这个四边形经过的所有点的集合为 S 1 S_1 S1​。 接下来在 O O O上取点 P 6 , P 7 , P 8 , P 9 P_6,P_7,P_8,P_9 P6​,P7​,P8​,P9​使得五边形 P 0 P 6 P 7 P 8 P 9 P_0P_6P_7P_8P_9 P0​P6​P7​P8​P9​是正五边形。记这个五边形的点集为 S 2 S_2 S2​。 中间省略 n − 2 n-2 n−2次操作。 最后在 O O O上取点 δ 1 , δ 2 , δ 3 , … , δ n \delta_1,\delta_2,\delta_3,…,\delta_n δ1​,δ2​,δ3​,…,δn​使得 n 1 n1 n1边形 P 0 δ 1 δ 2 δ 3 … δ n P_0\delta_1\delta_2\delta_3…\delta_n P0​δ1​δ2​δ3​…δn​是正 n 1 n1 n1边形。 记所有 P 0 δ 1 δ 2 δ 3 … δ n P_0\delta_1\delta_2\delta_3…\delta_n P0​δ1​δ2​δ3​…δn​上的非单一点的集合为 W ′ W W′。 非单一点的定义是 对于每一个点 S 0 , S 1 , … , S n − 1 S_0,S1,…,S{n-1} S0​,S1​,…,Sn−1​中任意一个集合包含了它 设这个点的坐标是 x , y x,y x,y则 x , y x,y x,y满足 x 2 y 2 R 2 x^2y^2R^2 x2y2R2
显然 P 0 P_0 P0​是一个非单一点。 记 W ′ W W′中元素的个数为 L ′ L L′。 输入格式 T T T组数据。 每一组数据只有一行输入 n n n。 输出格式 T T T行按顺序输出每个样例的 L ′ L L′。 样例 #1 样例输入 #1 1 9样例输出 #1 6提示 对于 100 % 100\% 100%的数据有 7 n 5 × 1 0 6 7n5\times10^6 7n5×106 1 ≤ T 5 × 1 0 6 1\leq T5\times10^6 1≤T5×106。 题解 传送门 如下。 题目 传送门 正解 单独讨论 M M M边形的情况。 不妨设 M M M边形的 M M M个点分别为 P 0 , P 1 , … , P M − 1 P_0,P1,…,P{M-1} P0​,P1​,…,PM−1​且外接圆心为 O O O半径为 R R R。 定义 ∠ P i O P 0 θ i \angle P_iOP_0\theta_i ∠Pi​OP0​θi​设 P 0 ( R , 0 ) P_0(R,0) P0​(R,0)。 则有 θ i 2 π i M \theta_i\frac{2\pi i}{M} θi​M2πi​。 那么我们可以求出 P i ( x i , y i ) P_i(x_i,y_i) Pi​(xi​,yi​) x i R cos ⁡ θ i , x_iR\cos\theta_i, xi​Rcosθi​, y i R sin ⁡ θ i . y_iR\sin\theta_i. yi​Rsinθi​. 那么我们回到原题。 由于非单一点的第二个条件我们得知它在圆 O O O上。 不妨设 N N N边形 N n 1 Nn1 Nn1的第 i i i个点与 K K K边形的第 j j j个点重合。 那么我们有 θ i θ j 2 k π \theta_i\theta_j2k\pi θi​θj​2kπ 2 π i N 2 π j K 2 k π , 1 ≤ j K N , i N \frac{2\pi i}{N}\frac{2\pi j}{K}2k\pi,1\leq jKN,i N N2πi​K2πj​2kπ,1≤jKN,iN i N j K k \frac{i}{N}\frac{j}{K}k Ni​Kj​k ∵ 0 ≤ i N 1 , 0 ≤ j K 1 \because 0\leq\frac{i}{N}1,0\leq\frac{j}{K}1 ∵0≤Ni​1,0≤Kj​1 ∴ k 0 \therefore k0 ∴k0 ∴ j N i K , i j N K \therefore jNiK,ij\frac{N}{K} ∴jNiK,ijKN​ 例如当 n 9 n9 n9时 N n 1 10 Nn110 Nn110符合的结果有 i 0 , c h o o s e j 0 i0,choose\ j0 i0,choose j0 i 1 , N o W a y i1,No\ Way i1,No Way i 2 , c h o o s e j 1 , K 5 i2,choose\ j1,K5 i2,choose j1,K5 i 3 , N o W a y i3,No\ Way i3,No Way i 4 , c h o o s e j 2 , K 5 i4,choose\ j2,K5 i4,choose j2,K5 i 5 , c h o o s e j 2 , K 4 i5,choose\ j2,K4 i5,choose j2,K4 i 6 , c h o o s e j 3 , K 5 i6,choose\ j3,K5 i6,choose j3,K5 i 7 , N o W a y i7,No\ Way i7,No Way i 8 , c h o o s e j 4 , K 5 i8,choose\ j4,K5 i8,choose j4,K5 i 9 , N o W a y i9,No\ Way i9,No Way 样例答案为 6 6 6。 假设 N β 1 α 1 β 2 α 2 … β n α n , β i β j w h e n i ≤ j , N\beta_1^{\alpha_1}\beta_2^{\alpha_2}…\beta_n^{\alpha_n},\beta_i\beta_j\ when\ i\leq j, Nβ1α1​​β2α2​​…βnαn​​,βi​βj​ when i≤j,且 β i \beta_i βi​为质数。 显然 i p M ipM ipM且 M β i β j … M\beta_i\beta_j… Mβi​βj​… β i \beta_i βi​可能与 β j , … \beta_j,… βj​,…相等 则有 j p , K N M jp,K\frac{N}{M} jp,KMN​。 显然 K N KN KN那么只需得 p N M p\frac NM pMN​。 那么我们就能发现非单一点的数量 L ′ L L′实质上是所有小于 N N N且不与 N N N互质的数字的数量再加一。 统计与 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 i2;iN;i)if(!a[i]){for(register int ji;jN;ji){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(n1-a[n1]);putchar(\n);}return 0; }