电子商务网站开发课程,免费商用图片的网站,it软件开发培训机构,做门用什么网站好problem
洛谷链接
solution
最后子集大小一定 ≥n−3\ge n-3≥n−3#xff0c;下面考虑证明这个结论。 假设 n2kn2kn2k。 ∏i1n(i!)∏i1k(2i−1)!(2i)!∏i1k(((2i−1)!)22i)∏i1k((2i−1)!)2⋅∏i1k2i∏i1k((2i−1)!)2⋅2k⋅k!\prod_{i1}^n(i!)\prod_{i1}^{k}(2i-1)!(2i)!\…problem
洛谷链接
solution
最后子集大小一定 ≥n−3\ge n-3≥n−3下面考虑证明这个结论。 假设 n2kn2kn2k。 ∏i1n(i!)∏i1k(2i−1)!(2i)!∏i1k(((2i−1)!)22i)∏i1k((2i−1)!)2⋅∏i1k2i∏i1k((2i−1)!)2⋅2k⋅k!\prod_{i1}^n(i!)\prod_{i1}^{k}(2i-1)!(2i)!\prod_{i1}^{k}\Big(\big((2i-1)!\big)^22i\Big)\prod_{i1}^k\big((2i-1)!\big)^2·\prod_{i1}^{k}2i\prod_{i1}^k\big((2i-1)!\big)^2·2^k·k!∏i1n(i!)∏i1k(2i−1)!(2i)!∏i1k(((2i−1)!)22i)∏i1k((2i−1)!)2⋅∏i1k2i∏i1k((2i−1)!)2⋅2k⋅k! k2tk2tk2t只用扔掉 k!k!k! 这一项就可以开出整根 ∏i1k(2i−1)!⋅2t\prod_{i1}^k(2i-1)!·2^t∏i1k(2i−1)!⋅2t。k2t1k2t1k2t1扔掉 k!k!k! 再多扔一个 2!2!2!仍可以开出上面的整根。 假设 n2k1n2k1n2k1。 直接扔掉 n!n!n!就转化到了 n′2kn2kn′2k 的情况。 且如果情况满足 n≡3(mod4)n\equiv3\pmod4n≡3(mod4)答案一定是扔掉 2!,n−12!,n!2!,\frac{n-1}{2}!,n!2!,2n−1!,n!。
这里只是证明的答案的下界但并非一定是最优答案的扔法通过样例可知。
接着我们需要考虑如何判断是否可以只用删除 1/21/21/2 个数。
要知道决定一个数是否是平方数的关键在于质因子的幂次是否都是偶数。
也就是说要在尽可能地少扔数条件下使得质因子幂次为奇数的都变成偶数。
只有出现次数的奇偶之分我们想到了 0/10/10/1。
两个数相乘对应质因子的幂次相加二进制的加法相当于 010101 的异或。
但不可能对于每一个 iii 都把 nnn 以内的质数都开一个空间然后储存奇偶之分再异或。时间空间总得挂一个。
1e61e61e6 以内的质数个数 $\approx\frac{n}{\ln n}\approx 78498 $。我们采用 异或哈希。
对每一个质数分配随机的 646464 位整型权值两个数的乘积变为两个数的哈希值的异或。
这样一来对于出现偶数次的质数异或后结果就是 000只有出现奇数次的质数的权值会呈现在结果中。
质数 iii 的哈希值记为 gig_igi同样还要知道 gi!g_{i!}gi!这是很好求的 gi!g(i−1)!⊕gig_{i!}g_{(i-1)!}\oplus g_igi!g(i−1)!⊕gi。
因为 111 肯定是必选的请直接从头到尾忽视。
如果 val⨁i2ngi!0val\bigoplus_{i2}^n g_{i!}0val⨁i2ngi!0则答案为 nnn。将 gi!g_{i!}gi! 通过 map 映射 iii。 如果 map 中存在一个值为 valvalval意味着可以删去这个 val→kval\rightarrow kval→k答案为 n−1n-1n−1。枚举删除的要删除的数 iii考虑 map 是否存在 val⊕gi!val\oplus g_{i!}val⊕gi!如果有则将这个映射的 kkk 一同删去答案为 n−2n-2n−2。 如果以上情况都没有发生那么应当是 n≡3(mod4)n\equiv 3\pmod4n≡3(mod4) 的情况直接删掉特定的三个数即可。
我也不知道这个哈希的冲撞概率是多少太菜了 so vegetable!
code
#include bits/stdc.h
using namespace std;
#define maxn 1000005
#define int long long
map int, int mp;
int n, cnt;
int f[maxn], g[maxn], prime[maxn];signed main() {mt19937_64 Rand( time( 0 ) );scanf( %lld, n );iota( prime 1, prime n 1, 1 );for( int i 2;i n;i ) if( prime[i] i ) {for( int j i;j n;j i )prime[j] min( prime[j], i );g[i] Rand();}for( int i 2;i n;i ) {f[i] f[i - 1];int x i;while( x ^ 1 ) {f[i] ^ g[prime[x]];x / prime[x]; }mp[f[i]] i;}auto solve [] ( int n ) - vector int {int ans 0;for( int i 2;i n;i ) ans ^ f[i];if( ! ans ) return {};if( mp.find( ans ) ! mp.end() ) return { mp[ans] };for( int i 2;i n;i )if( mp.find( ans ^ f[i] ) ! mp.end() ) return { i, mp[ans ^ f[i]] };return { 2, n - 1 1, n };};auto ans solve( n );printf( %lld\n, n - ans.size() );for( int i 1;i n;i )if( find( ans.begin(), ans.end(), i ) ans.end() ) printf( %lld , i );return 0;
}
