新普金娱乐网址


美妙到不现实,大都夭折的可怜轻易

书评|你无什么做好互联网

天文欧拉函数 BZOJ3884 上帝和聚集的正确用法

  • 九月 15, 2018
  • 天文
  • 没有评论

文/辰雪琳儿

3884: 上帝和聚集的是用法

Time Limit: 5 Sec  Memory Limit:
128 MB
Submit: 1843  Solved: 862
[Submit][Status][Discuss]

早已年少好狂,以为一花一叶便是相同社会风气。于是我们开心的过了咱们的中学时。那时的我们或总想在毕业遥遥无期,可瞬间就还各为东西,一首《同桌的卿》点来得了埋藏心底的同班情谊。

Description

冲局部修上之记载,上帝之相同糟糕失败的创世经历是这般的:

率先上,
上帝创造了一个社会风气之为主元素,称做“元”。

仲上,
上帝创造了一个新的因素,称作“α”。“α”被定义为“元”构成的联谊。容易觉察,一共发生少种植不同之“α”。

老三上,
上帝又创造了一个初的元素,称作“β”。“β”被定义也“α”构成的集。容易发现,一共发生四种植不同的“β”。

季上,
上帝创造了新的要素“γ”,“γ”被定义也“β”的集。显然,一共会发出16种植不同之“γ”。

倘依照这样下去,上帝创造的季栽素将会发65536种植,第五种植元素用见面时有发生2^65536栽。这将会见是一个天文数字。

然而,上帝并不曾预想到元素种类数之增进是这般的霎时。他想念要于世界之元素丰富起来,因此,日复一日,年复一年,他再地创建着新的要素……

可不久,当上帝创造出最后一种植元素“θ”时,他发现就世界之素实在是极度多了,以致吃世界之容量不足,无法接受。因此于及时同样龙,上帝毁灭了社会风气。

从那之后,上帝仍记得那不行失败的创世经历,现在他想念咨询问你,他最后一次于创的因素“θ”一共发生微种?

上帝觉得这数字或者过于巨大而望洋兴叹代表出来,因此你只有需要应这数对p取模后的价值即可。

若可当上帝从“α”到“θ”一共创造了10^9次因素,或10^18糟糕,或者索性∞次。

同句话题意:

天文 1

翻阅生涯十分枯燥,只容得生书本及试题;然而看生涯也为格外精美,可以针对爱的男性(女)生宣誓主权,也会见当课堂上及撞老师引发大战;还得大概上三五密友纵情高歌,唱尽心中悲与喜欢;也克以球场上纵情挥洒汗水、考场上奋笔疾书。想想那时候的确好得文武兼备,上懂天文下知地理。

 

时光荏苒,曾经的我们每朝东西,已然各谋前程。想来对于一些人要从事那无异软的个别竟变成了不可磨灭,曾经的许或只有是那时的随口拈来。

Input

接通下去T行,每行一个正整数p,代表你用取模的价

当今,辗转了解到之音信无不告诉我们那时候的同窗情谊只能深埋心底,各自安好便曾可。翻看毕业合影,如斯笑脸是那段时光最真实地形容,枯燥并开心着。不由得感叹要是能够回去那时该多好。现今只能挥一指挥手,告别那个属于我们的金黄时代,度过人生之青春雨季就待面对人生之风风雨雨。回想起来,曾经的老三八线、半块橡皮、尺子、碳素笔是那时候极端爱吸引战争之,不过无论是就的口水仗还是恨死得牙痒痒,都于毕业那一刻刺激消云散。

Output

T行,每行一个恰恰整数,为答案对p取模后的值

根源不同地方的兄弟姐妹聚集于一个几十平米的教室里,嬉笑怒骂,打打闹闹就这么咱们毕业了。同学录、合影成为了纪念之极致好措施,现在翻看起,也是大值得的。都说不过值得尊重的哪怕是中学上,友谊很实,笑容十分纯粹。如今常过境迁,有多少人还记得曾说了之时段不老,我们不清除。也许有同样上会相聚吧会见互诉别离,时光就是非一味,但我们或散了,那被时间洗尽铅华的面容与当时校园时稚嫩的脸蛋儿比,多了千篇一律卖成熟以及神,少了相同客青涩与童真。

Sample Input

3
2
3
6

回首向来萧瑟处,也任风雨也无晴。铭记那段时光,在漫漫人生路上留下自己一个念想。只愿曾经的校友、同窗各自安好。

Sample Output

0
1
4

HINT

对于100%的数据,T<=1000,p<=10^7

Source

By
PoPoQQQ

 

额……生书大佬

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int t,p;
 7 int oula(int x){
 8     int ans=x;
 9     for(int i=2;i*i<=x;i++)
10         if(!(x%i)){
11             ans=ans/i*(i-1);
12             while(!(x%i)) x/=i;
13         }
14     if(x^1) ans=ans/x*(x-1);
15     return ans;
16 }
17 long long qpow(long long a,long long b,long long mod){
18     long long ans=1;
19     for(;b;b>>=1,a=a*a%mod)
20         if(b&1) ans=ans*a%mod;
21     return ans;
22 }
23 long long solve(int x){
24     long long ans=0;
25     if(x==1) ans=0;
26     else{
27         int tmp=oula(x);
28         ans=qpow(2,solve(tmp)+tmp,x);
29     }
30     return ans;
31 }
32 int main(){
33     scanf("%d",&t);
34     while(t--){
35         scanf("%d",&p);
36         printf("%lld\n",solve(p));
37     }
38     return 0;
39 }

 

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图