一本通1629聰明的燕姿

1629：聰明的燕姿

時間限制: 1000 ms ??? ??? 內存限制: 524288 KB

【題目描述】

城市中人們總是拿著號碼牌，不停尋找，不斷匹配，可是誰也不知道自己等的那個人是誰。

可是燕姿不一樣，燕姿知道自己等的人是誰，因為燕姿數學學得好！燕姿發現了一個神奇的算法：假設自己的號碼牌上寫著數字?SS，那么自己等的人手上的號碼牌數字的所有正約數之和必定等于?S。

所以燕姿總是拿著號碼牌在地鐵和人海找數字（喂！這樣真的靠譜嗎）可是她忙著唱《綠光》，想拜托你寫一個程序能夠快速地找到所有自己等的人。

【輸入】

輸入包含?k?組數據。

對于每組數據，輸入包含一個號碼牌S。

【輸出】

對于每組數據，輸出有兩行，第一行包含一個整數?m，表示有?m?個等的人。

第二行包含相應的?m?個數，表示所有等的人的號碼牌。

注意：你輸出的號碼牌必須按照升序排列。

【輸入樣例】

42

【輸出樣例】

3
20 26 41

【提示】

數據范圍與提示

對于 100% 的數據，k≤100,?S≤2×10⁹?。

?

sol：這道題初看時毫無思路，于是去看題解了，看到是搜索后一臉懵逼。。。

對于一個數

如果他是p1^a1*p1^a2*p3^a3*~~*pn^an

那么他的因數和就是 （p1⁰+p1¹+p1²+...+p1^a1）*（p2⁰+p2¹+...+p2^a2）*...*（pn¹+pn²+...+pn^an）

于是可以爆搜p1~pn及其系數a1~an，隨便弄點小剪枝居然就能過了，而且還飛快

剪枝（1），令當前的因數和為S，若（S-1）為質數，那么（S-1）*之前的幾個系數顯然是一種答案

剪枝（2），令當前的因數和為S，枚舉質因數p，若p²>=S，這個p就是非法的，因為就算系數a是1， S除以（p+1）后S也小于p，而之后出現的質因數必須嚴格大于上一個（沒有這個剪枝會T的很慘）

Ps：代碼實現復雜度并不高

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-'); ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{if(x<0){putchar('-'); x=-x;}if(x<10){putchar(x+'0'); return;}write(x/10);putchar((x%10)+'0');return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=100005;
int Prim[N],P_Cnt;
bool Bo[N];
inline void Pre_Prime()
{Prim[P_Cnt=0]=0;int i,j;int B=100000;for(i=2;i<=B;i++){if(!Bo[i]){Prim[++P_Cnt]=i;}for(j=1;j<=P_Cnt&&Prim[j]*i<=B;j++){
//            printf("Shai %d*%d=%d\n",Prim[j],i,Prim[j]*i);Bo[Prim[j]*i]=1;if(i%Prim[j]==0) break;}}
//    printf("Cnt=%d\n",P_Cnt);
//    for(i=1;i<=P_Cnt;i++) Wl(Prim[i]);
//    exit(0);return;
}
int Num,Ans[N];
inline bool Check_Prime(int x)
{if(x<=100000) return (Bo[x])?(false):(true);int i;for(i=2;i*i<=x;i++) if(x%i==0){return false;}return true;
}
//(p1^0+p1^1+...+p1^a1)*(p2^0+p2^1+...+p2^a2)*...*(pn^0+pn^1+...+pn^an)
inline void dfs(int Last,int Shuz,int Sum)
{if(Sum==1){Ans[++*Ans]=Shuz; return;}if(Sum-1>Prim[Last]&&Check_Prime(Sum-1)){Ans[++*Ans]=Shuz*(Sum-1);}int i,j,t;for(i=Last+1;i<=P_Cnt&&Prim[i]*Prim[i]<=Sum;i++){t=Prim[i];for(j=t+1;j<=Sum;t*=Prim[i],j+=t) if(Sum%j==0){dfs(i,Shuz*t,Sum/j);}}return;
}
int main()
{Pre_Prime();while(~scanf("%d",&Num)){int i;*Ans=0;dfs(0,1,Num);sort(Ans+1,Ans+*Ans+1);*Ans=unique(Ans+1,Ans+*Ans+1)-Ans-1;Wl(*Ans);for(i=1;i<*Ans;i++){W(Ans[i]);}if(*Ans) Wl(Ans[*Ans]);}return 0;
}
/*
input
42
8359
output
3
20 26 41
0
*/

?