ACM一道题目 求大神给出解答 解释或者代码都行 谢谢~~~~~!

Problem Description
自从Czj上了初中,已经不再满足于从1数到100了,他打算来个高难度的挑战。
设a1=1,a2=11,有数列ai,任意1<i≤n,元素ai−1与其自身的最后一位数字组成了新的数字X(如233将会变成2333),而ai是X的最大质因子。由于Czj很懒,数到2333就觉得无聊而跑去写gc了。现在请你帮他完成这未竟的事业。
Input
第一行是一个正整数T(T<100),代表接下来有T次询问。
接下来的T行,每一行输入一个正整数i(1≤i≤104)。
Output
对于每次询问,你应该求出数组中的第i个元素ai,并以"Case #t: ai"的格式单独输出一行,不包括双引号。其中#t代表询问的编号。
Sample Input

3
5
6
7

Sample Output

Case #1: 23
Case #2: 233
Case #3: 2333

Author
SCNU20102200088

acm

2个回答

czj是谁?初中生不满足数数数到100了,汗。题目也不是这么胡编的

我先说笨的了…感觉核心是求质因数
但是每个几千的数求质数会累死的…
所以每次遍历时把质数取出来,存起来。
下次再求质数先从存好的质数里面取,再往下遍历,直到遍历出最佳结果,期间发现的质数也都存起来。
这个笨方法第一在求质数那里省了一点点时间,可以用表格去倍数的方法求质数。
第二个遍历出最大的质因数,要么是遍历到x开方,要么就是小于x所有质数遍历一遍……哪种都费劲。。。
我就知道这个笨方法……大家抛玉吧

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐