本蒟蒻终于开始接触数学了。。。之前写的都忘了。。。忽然想起来某神犇在几个月前就切了FWT了。。。
给出三个结论：
1.1-N中的反素数是1-N中约数最多但是最小的数
2.1-N中的所有数的质因子种类不超过10，质因子指数总和不超过30
简单说：2*3*5*7*11*13*17*19*23*27*29*31>2*1E+9,2^31>2*1E+9
3.最大反质数的质因子是连续的几个最小的质数，并且指数非严格单调递减
如果不是最小的几个质因子，或不连续，那最大的质因子都可以用更小的，或空缺的替换来使这个数变得更小
即p|x && q不能整除x，q<p && x=p^k*C ，则有更小的y=q^k*C，且x与y的约数相等
#include<cstdio> #include<iostream> #define R register int #define ll long long using namespace std; int n,num,ans; const int p[15]={1,2,3,5,7,11,13,17,19,23,29}; inline void dfs(int s,int cnt,int lst,int sums,ll sum) { if(sums>30) return ; if(s==10) { if(cnt>num) ans=sum,num=cnt; else if(cnt>=num&&sum<=ans) ans=sum,num=cnt; return ; } R t=1; for(R i=0;i<=lst;++i) {dfs(s+1,cnt*(i+1),sums+i+1,i,sum*t); t*=p[s]; if(sum*t>n) break;} } signed main() { scanf("%d",&n); dfs(1,1,30,0,1); printf("%d",ans); }
2019.05.07
BZOJ 1053 [HAOI2007]反素数ant 神奇的约数
原文：https://www.cnblogs.com/Jackpei/p/10824906.html