從這個FB開始寫博客啦。
也不知道會堅持多久……
http://www.lydsy.com/JudgeOnline/problem.php?id=3737
因為是好玩的數學題所以剛看見的時候就想捉了……但是無限耽擱這兩天才處理掉。
交上去各種瑕疵CE……
改好發現數組開小各種RE……
然後各種TLE……
小看數據了= =。
看到題拿各種公式套，似乎是按因數來搜索。咦用2的冪次作深度上界估計似乎能搜？用質數前綴積上界似乎更小？
然後就暴搜吧……
原理是對任意phi(x)=n的x，它的所有素因子-1的積必被n整除。
所以跟先找哪個就沒關系了，多了一個下界剪枝。
然後枚舉可能的質數的時候只要枚舉不超過sqrt（n）的……否則有兩種情況。
1、此時x有兩個及以上的素因數，那麼一定有一個素因數-1是n小於sqrt（n）的因數，不可能找完大於sqrt（n）再回過來找它……
2、x是質數，也就是特判一下n+1是不是質數了。
雖然把第二種情況加了Miller_Rabin還是T了……
WTF！太假了！
然後發現能卡我的大多是類似那些高合成數的……總之要判的n+1一般不大。
於是把素數表打大一點，n+1小的時候直接在表裡找就過了。
最後回過頭證明一下搜索能硬上……
設F(k)為前k個質數積，f為其反函數。易知搜索樹的寬度深度都是f(n) （n還要變小呢）
而f（n）的話……記得以前推出來是logn/loglogn，錯了求不D。
然後按傳統要羞恥地貼代碼喽？……估計不對著代碼看也蠻難看懂的。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long LL;
#define rep(i,j,n) for(int i=j;i<=n;i++)
char c;
template<class T> inline void read(T&x){for(c=getchar();c<'0'||c>'9';c=getchar());for(x=0;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';};
bool t[4010010];
LL n,p[1000000],ans[1000000];
int T,tot,tott,len,S=10;
void pre(){
memset(t,true,sizeof(t));
rep(i,2,4010000) if(t[i]){
p[++len]=i;
rep(j,i,4010000/i) t[i*j]=false;
}
}
inline LL muti_mod(LL a,LL b,LL c){
a%=c;
b%=c;
LL ret=0;
while(b){
if(b&1){ret+=a;if(ret>=c)ret-=c;}
a<<=1;
if(a>=c)a-=c;
b>>=1;
}
return ret;
}
inline LL pow_mod(LL x,LL n,LL mod){
if(n==1)return x%mod;
int bit[50],k=0;
while(n){
bit[k++]=n&1;
n>>=1;
}
LL ret=1;
for(;k>0;k--){
ret=muti_mod(ret,ret,mod);
if (bit[k-1]==1) ret=muti_mod(ret,x,mod);
}
return ret;
}
inline bool check(LL a,LL n,LL x,LL t){
LL ret=pow_mod(a,x,n),last=ret;
for(int i=1;i<=t;i++){
ret=muti_mod(ret,ret,n);
if(ret==1&&last!=1&&last!=n-1) return true;
last=ret;
}
if(ret!=1) return true;
return false;
}
inline bool prime(LL n){
if(n<2)return false;
if(n==2)return true;
if((n&1)==0) return false;
LL x=n-1;LL t=0;
while((x&1)==0){x>>=1;t++;}
for(int i=0;i<S;i++)
{
LL a=rand()%(n-1)+1;
if(check(a,n,x,t)) return false;
}
return true;
}
void find(LL n,int list,LL now){
if(n==1){ans[tot++]=now;return;}
if(1&n) return;
LL N=now,m,maxi=int(sqrt(n))+1;
rep(i,list,len) if(p[i]>maxi)break;else if(n%(p[i]-1)==0){
m=n/(p[i]-1);
N*=p[i];
find(m,i+1,N);
while(m%p[i]==0){
m/=p[i];N*=p[i];
find(m,i+1,N);
}
N=now;
}
if(n+1>=p[list]){
if(n+1>p[len]){if(prime(n+1))ans[tot++]=N*(n+1);}
else{if(t[n+1])ans[tot++]=N*(n+1);}
}
}
int main()
{
read(T);
pre();
while(T--){
read(n);tot=0;
if(1&n){
if(n==1){puts("2");puts("1 2");}else puts("0"),puts("");
continue;
}
find(n,1,1);
sort(ans,ans+tot);
printf("%d\n",tot);
rep(i,0,tot-2) printf("%lld ",ans[i]);
if(tot)printf("%lld\n",ans[tot-1]);else{puts("");};
}
}
沒有度數為奇數的頂點的圖含有歐拉回路.Kn當n是奇數時,每個頂點的度都是n-1是偶數,此時Kn含有歐拉回路.
只有兩個度數為奇數的頂點的圖有歐拉路但沒有歐拉回路.由上題,n不能是奇數,n是偶數時,Kn有n個度數為奇數的頂點,所以n=2.
第一個 N是 3第二個N是 2吧 ？
