紛菲幻劍錄 之 十年一劍
Time Limit: 10000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 497 Accepted Submission(s): 299
Problem Description
黃沙點點揚劍處，流光一瞬已千年......
帶著最初的夢想，穿過孤煙大漠，踏進這個繁雜的中原，心中的目標始終不曾改變......
(以上是亦紛菲感人肺腑的吟詩,字字珠玑,句句懇切)
(以下是ZTY描述的中原故事虛構：大意是滅“深犬”-_-||，救pacision)
說時遲,那時快,亦紛菲拿出他的幻劍向深犬刺去,可惜啊可惜~~可惜什麼呢? 那麼我們先來進m段廣告,每段廣告又分為s段小廣告(因為廣告太費時間, 而且試問做題的時候怎麼能看廣告呢,所以這裡就把廣告這一段略去了,不知大家意下如何? 如果同意的話那就繼續讀題)話說當時亦紛菲拿出他的幻劍向深犬刺去, first blood !可惜事情並沒有那麼簡單, 眼看深犬奄奄一息之時,天上下起了甘露,"深犬進化!"深犬大喊, "迭代深犬!!!", 原來深犬汲取日月之精華,天地之靈氣, 進化成了無堅不摧,以一敵萬的"迭代深犬",亦紛菲知道此時的他已然不敵,於是萬般無奈之下他決定暫避鋒芒,使出一招"凌波微步",消失在燈火闌珊處,誰料亦紛菲的幻劍竟然留在了迭代深犬那裡,又不好意思回去拿,只好求助<英雄哪裡出來>,<英雄哪裡出來>是一位隱藏人物,據說出沒於幽雲十六州，由於世俗紛爭，是故退隱山林，因為十年前遇上亦紛菲,又因為一飯之恩以幻劍相贈,可惜鑄造幻劍需要一把以類鑄成的寶劍鑲上h(1 <= h <= n)顆壯志凌雲石方可鑄造成功,於是亦紛菲花了五年寫了個類,並且將之鑄成寶劍,再去找<英雄哪裡出來>,這時<英雄哪裡出來>說五年前他說的話中有錯別字,是"以淚鑄成的寶劍", 而不是"以類鑄成的寶劍","挫折,真的是人生要走的路嗎?"亦紛菲耳邊回蕩起這句話,但試問亦紛菲又怎麼會輕言放棄, 又是五年不眠不休鑄造出了"以淚鑄成的寶劍"(所謂“以淚鑄成的寶劍”的特殊之處在於它的每一個部分都是一個數字1，共有g個部分，當g == 3，就是111，g == 4 時，就是1111，而且要保證它能夠鑄成幻劍的必要條件是由g必須為素數，比如3為素數，所以它有機會成為幻劍，但是這僅僅是必要條件),接下來的工作找到h顆壯志凌雲石,但是<英雄哪裡出來>給了亦紛菲 n(3 <= n <= 20000)顆壯志凌雲石,每顆都有顏色,用一個正整數t(0 <= t <= n)來表示,將這些石頭排成一排，讓你挑出其中連續的h顆,但是壯志凌雲石之間有"異元互質"作用,聽黑衣人說,如果h顆滿足"靈異約束",那麼他們之間沒有"異元互質",是可以鑄成幻劍的，所謂靈異約束就是說任意選擇連續h顆,總和sum % n == 0 則稱這h顆石頭滿足靈異約束。
(以下是亦紛菲親筆)
材料已有還需打造之法，詢問<英雄哪裡出來>，想要得知打造之法需要回答<英雄哪裡出來>的一個問題。題意是 給你2個整數 x,k. (1<=x<6400000 && 0<k<=2^31-1)，要你找出 x 的第k大 素因子（如果不存在回答"no"）for example x=48, k=6. 48分解的{2,2,2,2,3} 所以1-4大素因子都是2，第5大是3，比5大則沒有,
成功鑄得幻劍後，挑戰深犬。 但深犬也要你回答一道題目方能和接受你的挑戰（-_-||汗~~~），題意是這樣的，用劍氣在懸崖壁上刻出2^n
(1=<n<=20000);
當然這對亦紛菲來說自然是不在話下,輕松解決,於是大戰猶如箭在弦上,一觸即發!
(待續...)
Input
現在的亦紛菲已然不是當時的亦紛菲，但是對於曾經的一切一切歷歷在目，於是他打算模擬一下當時的情景以慰深犬在天之靈，亦紛菲現在要做的工作是:
1.判斷一把劍是否有機會成為幻劍
2.找出符合題意的壯志凌雲石
3.從<英雄哪裡出來>口中得知打造之法
4.回答深犬的問題
首先輸入一個字符串Str，該字符串有四種形式：
(1)Swords 然後跟一個整數num,該數字全部由1組成,保證數字長度小於一百;
(2)Stones 然後跟一個整數n(3 <= n <= 20000),接下來一行輸入n個數字;
(3)Search 然後跟著2個整數x,k,(1<=x<6400000 && 0<k<=2^31-1);
(4)See 然後跟著1個整數n,(1=<n<=16000);
Output
對於每個字符串分別處理:
(1)Swords 輸出亦紛菲對num的判斷,如果num所代表的寶劍有機會成為幻劍輸出"Yes.",否則輸出"No.";
(2)Stones 輸出被亦紛菲選中的壯志凌雲石的下標(遞增輸出,兩個之間有一個空格),如果有多個答案,那麼滿足以下優先級,
首先如果存在多個滿足條件的序列，那麼輸出長度最小的(即題目中h最小的)，若果還是有多解，那麼輸出下標之和最小的；
如果不能找到,那麼輸出"可憐的亦紛菲!".
(3)輸出 x 的第k大素因子(如果不存在輸出 "no").
(4)輸出 一個整數 2^n .
Sample Input
Swords 11111
Swords 1111
Stones 4
1 3 3 4
Stones 6
1 1 1 1 1 1
Search
3 1
Search
6 2
Search
48 6
See
2
See
20
Sample Output
Yes.
No.
4
1 2 3 4 5 6
3
3
no
4
1048576
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=20000+10;
const int Base=10000;
int s[MAX],n;//s[j]記錄的前i個數mod n為j的最後一個位置
char str[110];
int temp[3000],sum[3000],A[3000];
bool prime[110];
void Prime(){
prime[1]=true;
for(int i=2;i*2<=100;++i)prime[i*2]=true;
for(int i=3;i*i<=100;++i){
if(!prime[i]){
for(int j=i*i;j<=100;j+=2*i)prime[j]=true;
}
}
}
int factor(int x,int k){
int num=0;
while(x%2 == 0)++num,x=x/2;
if(num>=k)return 2;
for(int i=3;i*i<=x;i+=2){
if(x%i == 0){
while(x%i == 0)++num,x=x/i;
if(num>=k)return i;
}
}
if(x != 1)++num;
if(num>=k)return x;
return 0;
}
void Mult(int *A,int *B){
int l=A[0]+B[0]-1,i,j,k;
memset(temp,0,sizeof(int)*(l+3));
for(i=1,k=1;i<=A[0];++i){
k=i;
if(A[i]){//為0本次就不用計算了
for(j=1;j<=B[0];++j,++k){
temp[k]+=A[i]*B[j];
if(temp[k]>=Base){
temp[k+1]+=temp[k]/Base;
temp[k]=temp[k]%Base;
}
}
}
}
while(temp[k]>=Base){
temp[k+1]+=temp[k]/Base;
temp[k]=temp[k++]%Base;
}
if(!temp[k])--k;
A[0]=k;
for(i=1;i<=k;++i)A[i]=temp[i];
}
void FastPow(int k){
sum[0]=1,sum[1]=1;
A[0]=1,A[1]=2;
while(k){
if(k&1)Mult(sum,A);
Mult(A,A);
k>>=1;
}
}
void problem1(){
scanf("%s",str);
int num=strlen(str);
if(!prime[num])printf("Yes.\n");
else printf("No.\n");
}
void problem2(){
int a,l=INF,p,k,t=0;
scanf("%d",&n);
memset(s+1,-1,sizeof(int)*(n+1));
s[0]=0;
for(int i=1;i<=n;++i){
scanf("%d",&a);
p=(t+a)%n;
if(s[p] != -1)if(i-s[p]<l)l=i-s[p],k=s[p]+1;//k記錄滿足條件的開始位置
s[p]=i;
t=p;
}
if(l == INF)printf("可憐的亦紛菲!\n");
else{
for(int i=k;i<k+l-1;++i)printf("%d ",i);
printf("%d\n",k+l-1);
}
}
void problem3(){
int x,k;
scanf("%d%d",&x,&k);
int temp=factor(x,k);
if(temp)printf("%d\n",temp);
else printf("no\n");
}
void problem4(){
scanf("%d",&n);
FastPow(n);
printf("%d",sum[sum[0]]);
for(int i=sum[0]-1;i>0;--i)printf("%04d",sum[i]);
printf("\n");
}
int main(){
Prime();
while(~scanf("%s",str)){
if(strcmp(str,"Swords") == 0)problem1();
else if(strcmp(str,"Stones") == 0)problem2();
else if(strcmp(str,"Search") == 0)problem3();
else problem4();
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=20000+10;
const int Base=10000;
int s[MAX],n;//s[j]記錄的前i個數mod n為j的最後一個位置
char str[110];
int temp[3000],sum[3000],A[3000];
bool prime[110];
void Prime(){
prime[1]=true;
for(int i=2;i*2<=100;++i)prime[i*2]=true;
for(int i=3;i*i<=100;++i){
if(!prime[i]){
for(int j=i*i;j<=100;j+=2*i)prime[j]=true;
}
}
}
int factor(int x,int k){
int num=0;
while(x%2 == 0)++num,x=x/2;
if(num>=k)return 2;
for(int i=3;i*i<=x;i+=2){
if(x%i == 0){
while(x%i == 0)++num,x=x/i;
if(num>=k)return i;
}
}
if(x != 1)++num;
if(num>=k)return x;
return 0;
}
void Mult(int *A,int *B){
int l=A[0]+B[0]-1,i,j,k;
memset(temp,0,sizeof(int)*(l+3));
for(i=1,k=1;i<=A[0];++i){
k=i;
if(A[i]){//為0本次就不用計算了
for(j=1;j<=B[0];++j,++k){
temp[k]+=A[i]*B[j];
if(temp[k]>=Base){
temp[k+1]+=temp[k]/Base;
temp[k]=temp[k]%Base;
}
}
}
}
while(temp[k]>=Base){
temp[k+1]+=temp[k]/Base;
temp[k]=temp[k++]%Base;
}
if(!temp[k])--k;
A[0]=k;
for(i=1;i<=k;++i)A[i]=temp[i];
}
void FastPow(int k){
sum[0]=1,sum[1]=1;
A[0]=1,A[1]=2;
while(k){
if(k&1)Mult(sum,A);
Mult(A,A);
k>>=1;
}
}
void problem1(){
scanf("%s",str);
int num=strlen(str);
if(!prime[num])printf("Yes.\n");
else printf("No.\n");
}
void problem2(){
int a,l=INF,p,k,t=0;
scanf("%d",&n);
memset(s+1,-1,sizeof(int)*(n+1));
s[0]=0;
for(int i=1;i<=n;++i){
scanf("%d",&a);
p=(t+a)%n;
if(s[p] != -1)if(i-s[p]<l)l=i-s[p],k=s[p]+1;//k記錄滿足條件的開始位置
s[p]=i;
t=p;
}
if(l == INF)printf("可憐的亦紛菲!\n");
else{
for(int i=k;i<k+l-1;++i)printf("%d ",i);
printf("%d\n",k+l-1);
}
}
void problem3(){
int x,k;
scanf("%d%d",&x,&k);
int temp=factor(x,k);
if(temp)printf("%d\n",temp);
else printf("no\n");
}
void problem4(){
scanf("%d",&n);
FastPow(n);
printf("%d",sum[sum[0]]);
for(int i=sum[0]-1;i>0;--i)printf("%04d",sum[i]);
printf("\n");
}
int main(){
Prime();
while(~scanf("%s",str)){
if(strcmp(str,"Swords") == 0)problem1();
else if(strcmp(str,"Stones") == 0)problem2();
else if(strcmp(str,"Search") == 0)problem3();
else problem4();
}
return 0;
}
