FancyCoder男人八题题解

名字是我瞎起的……

[UPD 4.14]我也是一个男人了哈哈哈哈

最近有点忙，很久没来，除个草
[BZOJ4802]Pollard-rho直接上
[BZOJ4803]大力搜索，大于1e7的质数判掉

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e7+7;
const int BASE[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
LL mul(LL a, LL b, LL P) {
	LL t = (a * b - LL((long double)a / P * b + 1e-3) * P) % P;
	return t < 0 ? t + P : t;
}
LL pw(LL x,LL k,LL mo){
	LL ans=1;
	for(;k;k>>=1){
		if(k&1)ans=mul(ans,x,mo)%mo;
		x=mul(x,x,mo)%mo;
	}
	return ans%mo;
}
bool check(long long n,int base) {
    long long n2=n-1,res;
    int s=0;
    while(n2%2==0) n2>>=1,s++;
    res=pw(base,n2,n);
    if((res==1)||(res==n-1)) return 1;
    while(s--) {
        res=mul(res,res,n);
        if(res==n-1) return 1;
    }
    return 0; // n is not a strong pseudo prime
}
bool isprime(const long long &n) {
    if(n==2)
        return true;
    if(n<2 || n%2==0)
        return false;
    for(int i=0;i<12&&BASE[i]<n;i++){
        if(!check(n,BASE[i]))
            return false;
    }
    return true;
}
bool minp[maxn];
LL p[maxn];
void sieve(){
	for(int i=2;i<maxn;i++){
		if(!minp[i]){
			minp[i]=1;
			p[++p[0]]=i;
		}
		for(int j=1;j<=p[0]&&(LL)i*p[j]<maxn;j++){
			minp[i*p[j]]=1;
			if(i%p[j]==0)
				break;
		}
	}
}
vector<LL>ans;
int k;
void print(){
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	for(int i=0;i<k&&i<ans.size();i++)
		printf("%lld%c",ans[i]," \n"[i+1==k]);
	exit(0);
}
LL bound=1e7;
void dfs(LL phin,int id,LL curn){
//	if(id)cerr<<phin<<" "<<id<<" "<<p[id]<<" "<<curn<<endl;
	if(phin>bound&&isprime(phin+1)){
		dfs(1,id-1,curn*(phin+1));
		//ans.push_back(curn*(phin+1));
		//if(ans.size()==k)print();
		//return ;
	}
	if(phin==1){
		ans.push_back(curn);
		if(curn%2)
			ans.push_back(curn*2);
		//if(ans.size()==k)print();
		return ;
	}
	if(!id)return ;
	
	if(phin%(p[id]-1)==0){
		LL pk=p[id];
		for(int i=1;;i++){
			if(phin%((pk/p[id])*(p[id]-1))==0)
				dfs(phin/(pk/p[id])/(p[id]-1),id-1,curn*pk);
			else break;
			pk*=p[id];
		}
		dfs(phin,id-1,curn);
	}else{
		while(id>=1&&phin%(p[id]-1)!=0)
			id--;
		dfs(phin,id,curn);
	}
}


LL _phi(LL n){
	LL ans=1;
	for(LL i=2;i*i<=n;i++){
		if(n%i==0){
			ans*=i-1;
			n/=i;
			while(n%i==0)ans=ans*i,n/=i;
		}
	}
	if(n>1)ans=ans*(n-1);
	return ans;
}

int bf(int phin){
	for(int i=1;i<1e5;i++)
		if(_phi(i)==phin){
			return i;
		}
	return -1;
}

LL calc(LL phin){
	dfs(phin,p[0],1);
	sort(ans.begin(),ans.end());
	if(ans.empty()||ans[0]>(1LL<<31))
		return -1;
	return ans[0];
}
int main(){
	sieve();
//cerr<<_phi(141538889898505LL)<<endl;
	LL phin;
	cin>>phin>>k;
//	bound=(LL)sqrt(phin)+2;
	//cin>>k;
	dfs(phin,p[0],1);
	print();
	//cout<<bf(phin)<<endl;
	/*sort(ans.begin(),ans.end());
	if(ans.empty()||ans[0]>(1LL<<31))puts("-1");
	else cout<<ans[0]<<endl;*/
	//print();
	return 0;
}

[BZOJ4804]结果是 $\sum_{i=1}^n F(i){\lfloor \frac{n}{i} \rfloor}^2 $ 其中 $F(n)=\sum_{d|n}\varphi(d)\mu(\frac{n}{d})$
[BZOJ4805]裸杜教筛
[BZOJ4806]dp[i][j][k]表示前i行有j列炮的数量为0，k列为1，转移也很简单
[BZOJ4807]C(n,m) mod 10**50,质因数分解，高精度
[BZOJ4808]最大独立集，染色流流流
[BZOJ4809]位运算加速暴力