hdu 5279 Reflect phi 欧拉函数-白红宇

hdu 5279 Reflect phi 欧拉函数

阅读量：4971 次

发布时间：2019-06-12

本文共 1497 字，大约阅读时间需要 4 分钟。

Reflect

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=628&pid=1003

Description

从镜面材质的圆上一点发出一道光线反射NN次后首次回到起点。 问本质不同的发射的方案数。

Input

第一行一个整数T，表示数据组数。T \leq 20T≤20 对于每一个组，第一行一个整数n(1 \leq n \leq 100)n(1≤n≤100)，接下来第二行nn个数允许前导零的非负整数A_iAi，表示数列。保证A_iAi位数\leq 100≤100。

Output

对于每一个组，输出共一行，包含一个整数，表示答案。

Sample Input

1 4

Sample Output

HINT

题意

题解：

暴力打表就好了

然后发现是欧拉函数phi

然后猜了一发结论交了一发

AC了

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 typedef long long LL;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 2000001#define mod 10007#define eps 1e-9const int inf=0x7fffffff; //无限大/**///**************************************************************************************inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}LL phi[maxn],n;void phi1(){ memset(phi,0,sizeof(phi)); phi[1]=1; for(LL i=2;i<=n;i++) { if(!phi[i]) { for(LL j=i;j<=n;j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } }}int main(){ int t=read(); n=1000010; phi1(); while(t--) { int x=read(); cout<
                  
                   <