数学专题

素数，整数分解，欧拉函数

1.poj 1365

题目给出num分解成几个素数相乘的形式，求num-1分解的形式

pow用的有点233

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 typedef long long ll;
 13 #define cl(a) memset(a,0,sizeof(a))
 14 #define ts printf("
*****
");
 15 #define sc(a) scanf("%d",&a);
 16 #define pt(a) printf("%d
",a);
 17 #define ff for(i=0;i<n;i++)
 18 #define fff for(i=0;i<n;i++) for(j=0;j<n;j++)
 19 const int MAXN=100005;
 20 
 21 //define single variable
 22 
 23 int n,m,tt;
 24 int ans,sum1,sum2,tot,Max;
 25 
 26 
 27 //define arrays
 28 int a[MAXN],b[MAXN];
 29 char s[MAXN];
 30 int vis[MAXN];
 31 //define struct
 32 struct Node
 33 {
 34     int x,y;
 35     Node(){}
 36     /*Node(int xx,int yy,int tt)
 37     {
 38 
 39     }*/
 40     void in()
 41     {
 42         scanf("%d%d",&x,&y);
 43     }
 44 }node[MAXN];
 45 
 46 //others
 47 bool cmp(Node a,Node b)
 48 {
 49     return a.y>b.y;
 50 }
 51 int prime[MAXN+1];
 52 void getPrime()
 53 {
 54 memset(prime,0,sizeof(prime));
 55 for(int i=2;i<=MAXN;i++)
 56 {
 57 if(!prime[i])prime[++prime[0]]=i;
 58 for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)
 59 {
 60 prime[prime[j]*i]=1;
 61 if(i%prime[j]==0) break;
 62 }
 63 }
 64 }
 65 long long factor[100][2];
 66 int fatCnt;
 67 int getFactors(long long x)
 68 {
 69 fatCnt=0;
 70 long long tmp=x;
 71 for(int i=1;prime[i]<=tmp/prime[i];i++)
 72 {
 73 factor[fatCnt][1]=0;
 74 if(tmp%prime[i]==0)
 75 {
 76 factor[fatCnt][0]=prime[i];
 77 while(tmp%prime[i]==0)
 78 {
 79 factor[fatCnt][1]++;
 80 tmp/=prime[i];
 81 }
 82 fatCnt++;
 83 }
 84 }
 85 if(tmp!=1)
 86 {
 87 factor[fatCnt][0]=tmp;
 88 factor[fatCnt++][1]=1;
 89 }
 90 return fatCnt;
 91 }
 92 void init()
 93 {
 94     ans=0,sum1=0,sum2=0,tot=0,Max=0;
 95     //cl(vis);
 96     //cl(node);
 97 }
 98 
 99 void fun(int x)
100 {
101     int num=getFactors((ll)x);
102     printf("%lld %lld",factor[num-1][0],factor[num-1][1]);
103     for(int i=num-2;i>=0;i--)
104     {
105         printf(" %lld %lld",factor[i][0],factor[i][1]);
106     }
107     printf("
");
108 }
109 int main()
110 {
111     int i,j,k,ca=1;
112     #ifndef ONLINE_JUDGE
113     freopen("1.in","r",stdin);
114     #endif
115     getPrime();
116     /*scanf("%d",&tt);
117     while(tt--)
118     {
119     //printf("Case %d: ",ca++);
120         init();
121     }*/
122     char ch;
123     while(scanf("%c",&ch)!=EOF)
124     {
125         init();
126         if(ch=='0')
127         {
128             break;
129         }
130         ans=ch-'0';
131         double sum=1;
132         bool flag=0;    //底数输入
133         while(1)
134         {
135             scanf("%c",&ch);
136             if(ch=='
')
137             {
138                 sum*=pow((double)ans,(double)tot);
139                 fun((int)sum-1);
140                 sum=1,ans=0,tot=0;
141                 break;
142             }
143             else if(ch==' '&&flag==0)
144             {
145                 flag=1;
146             }
147             else if(ch==' '&&flag==1)
148             {
149                 sum*=pow(ans,tot);
150                 ans=0;
151                 tot=0;
152                 flag=0;
153             }
154             else if(flag==0)
155             {
156                 ans=ans*10+(ch-'0');
157             }
158             else if(flag==1)
159             {
160                 tot=tot*10+(ch-'0');
161             }
162         }
163     }
164 }

View Code

2.poj 1365

给出一段范围和一个deep，对于任何长度为i(i<=deep)的一段连续数字都为合数，求字典序最小的一段

一开始以为可以直接贪心填，后来发现不一定，改用dfs

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 typedef long long ll;
 13 #define cl(a) memset(a,0,sizeof(a))
 14 #define ts printf("
*****
");
 15 #define sc(a) scanf("%d",&a);
 16 #define pt(a) printf("%d
",a);
 17 #define ff for(i=0;i<n;i++)
 18 #define fff for(i=0;i<n;i++) for(j=0;j<n;j++)
 19 const int MAXN=1005;
 20 
 21 //define single variable
 22 
 23 int n,m,tt;
 24 int ans[MAXN],sum[MAXN],sum1,sum2,tot,Max;
 25 bool notprime[1000010];//值为false表示素数，值为true表示非素数
 26 void Init()
 27 {
 28 memset(notprime,false,sizeof(notprime));
 29 notprime[0]=notprime[1]=true;
 30 for(int i=2;i<1000010;i++)
 31 if(!notprime[i])
 32 {
 33 if(i>1000010/i)continue;//防止后面i*i溢出(或者i,j用long long)
 34 //直接从i*i开始就可以，小于i倍的已经筛选过了,注意是j+=i
 35 for(int j=i*i;j<1000010;j+=i)
 36 notprime[j]=true;
 37 }
 38 }
 39 
 40 //define arrays
 41 int a[MAXN],b[MAXN];
 42 char s[MAXN];
 43 int vis[MAXN];
 44 
 45 void init()
 46 {
 47     sum1=0,sum2=0,tot=0,Max=0;
 48     cl(vis);
 49     cl(sum);
 50     cl(ans);
 51 }
 52 int l1,l2,deep,num;
 53 bool kk=0;
 54 void dfs(int pos)
 55 {
 56     if(kk)  return;
 57     if(pos==num+1)
 58     {
 59         kk=1;
 60         for(int i=1;i<=num;i++)
 61         {
 62             ans[i]=a[i];
 63         }
 64         return;
 65     }
 66     for(int i=l1;i<=l2;i++)
 67     {
 68         if(!vis[i])
 69         {
 70             int flag=1;
 71             for(int j=deep;j>=2;j--)
 72             {
 73                 if(!notprime[i+sum[pos-1]-sum[pos-j]])
 74                 {
 75                     flag=0;
 76                     break;
 77                 }
 78             }
 79             if(!flag)   continue;
 80             sum[pos]=sum[pos-1]+i;
 81             vis[i]=1;
 82             a[pos]=i;
 83             dfs(pos+1);
 84             vis[i]=0;
 85         }
 86     }
 87 }
 88 int main()
 89 {
 90     int i,j,k,ca=1;
 91     #ifndef ONLINE_JUDGE
 92     freopen("1.in","r",stdin);
 93     #endif
 94     Init();
 95     while(scanf("%d%d%d",&l1,&l2,&deep)!=EOF&&l1&&l2&&deep)
 96     {
 97         init();
 98         kk=0;
 99         num=l2-l1+1;
100         for(i=l1;i<=l2;i++)
101         {
102             vis[i]=1;
103             a[1]=i;
104             sum[1]=i;
105             dfs(2);
106             vis[i]=0;
107             if(kk)  break;
108         }
109         if(kk)
110         {
111             printf("%d",ans[1]);
112             for(i=2;i<=num;i++)
113             {
114                 printf(",%d",ans[i]);
115             }
116             printf("
");
117         }
118         else puts("No anti-prime sequence exists.");
119     }
120     return 0;
121 }

View Code

3.poj 2739

给出一个数，问能有几种连续素数和形式表示的方式，求一下前缀和，然会枚举首尾即可

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 typedef long long ll;
 13 #define cl(a) memset(a,0,sizeof(a))
 14 #define ts printf("
*****
");
 15 #define sc(a) scanf("%d",&a);
 16 #define pt(a) printf("%d
",a);
 17 #define ptn printf("
");
 18 #define ff for(i=0;i<n;i++)
 19 #define fff for(i=0;i<n;i++) for(j=0;j<n;j++)
 20 const int MAXN=10005;
 21 
 22 //define single variable
 23 
 24 int n,m,tt;
 25 int ans,sum[MAXN],sum1,sum2,tot,Max;
 26 
 27 
 28 //define arrays
 29 int a[MAXN],b[MAXN];
 30 char s[MAXN];
 31 int vis[MAXN];
 32 //define struct
 33 struct Node
 34 {
 35     int x,y;
 36     Node(){}
 37     /*Node(int xx,int yy,int tt)
 38     {
 39 
 40     }*/
 41     void in()
 42     {
 43         scanf("%d%d",&x,&y);
 44     }
 45 }node[MAXN];
 46 
 47 //others
 48 bool cmp(Node a,Node b)
 49 {
 50     return a.y>b.y;
 51 }
 52 
 53 int prime[MAXN+1];
 54 void getPrime()
 55 {
 56 memset(prime,0,sizeof(prime));
 57 for(int i=2;i<=MAXN;i++)
 58 {
 59 if(!prime[i])prime[++prime[0]]=i;
 60 for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)
 61 {
 62 prime[prime[j]*i]=1;
 63 if(i%prime[j]==0) break;
 64 }
 65 }
 66 }
 67 
 68 void init()
 69 {
 70     ans=0,sum1=0,sum2=0,tot=0,Max=0;
 71     //cl(vis);
 72 }
 73 
 74 
 75 int main()
 76 {
 77     int i,j,k,ca=1;
 78     #ifndef ONLINE_JUDGE
 79     freopen("1.in","r",stdin);
 80     #endif
 81 
 82     /*scanf("%d",&tt);
 83     while(tt--)
 84     {
 85     //printf("Case %d: ",ca++);
 86         init();
 87     }*/
 88     getPrime();
 89     sum[0]=0;
 90     for(i=1;i<=prime[0];i++)
 91         {
 92             sum[i]=sum[i-1]+prime[i];
 93         }
 94     while(scanf("%d",&n)!=EOF&&n)
 95     {
 96         //printf("Case %d: ",ca++);
 97         init();
 98         for(i=0;i<prime[0];i++)
 99         {
100             for(j=i+1;j<=prime[0];j++)
101             {
102                 if(sum[j]-sum[i]==n)    ans++;
103             }
104         }
105         pt(ans);
106     }
107 }

View Code

4.poj 1595

给出一个数，需要你求出其区间中的所有素数，然后再分素数个数的奇偶性，从素数列表的中间开始输出即可！二分找素数个数，然后确定起点位置输出即可

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 typedef long long ll;
 13 #define cl(a) memset(a,0,sizeof(a))
 14 #define ts printf("
*****
");
 15 #define sc(a) scanf("%d",&a);
 16 #define pt(a) printf("%d
",a);
 17 #define ptn printf("
");
 18 #define ff for(i=0;i<n;i++)
 19 #define fff for(i=0;i<n;i++) for(j=0;j<n;j++)
 20 const int MAXN=10005;
 21 
 22 //define single variable
 23 
 24 int n,m,tt;
 25 int ans,sum[MAXN],sum1,sum2,tot,Max;
 26 
 27 
 28 //define arrays
 29 int a[MAXN],b[MAXN];
 30 char s[MAXN];
 31 int vis[MAXN];
 32 //define struct
 33 struct Node
 34 {
 35     int x,y;
 36     Node(){}
 37     /*Node(int xx,int yy,int tt)
 38     {
 39 
 40     }*/
 41     void in()
 42     {
 43         scanf("%d%d",&x,&y);
 44     }
 45 }node[MAXN];
 46 
 47 //others
 48 bool cmp(Node a,Node b)
 49 {
 50     return a.y>b.y;
 51 }
 52 
 53 int prime[MAXN+1];
 54 void getPrime()
 55 {
 56 memset(prime,0,sizeof(prime));
 57 for(int i=2;i<=MAXN;i++)
 58 {
 59 if(!prime[i])prime[++prime[0]]=i;
 60 for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)
 61 {
 62 prime[prime[j]*i]=1;
 63 if(i%prime[j]==0) break;
 64 }
 65 }
 66 }
 67 
 68 void init()
 69 {
 70     ans=0,sum1=0,sum2=0,tot=0,Max=0;
 71     //cl(vis);
 72 }
 73 
 74 
 75 int main()
 76 {
 77     int i,j,k,ca=1;
 78     #ifndef ONLINE_JUDGE
 79     freopen("1.in","r",stdin);
 80     #endif
 81 
 82     /*scanf("%d",&tt);
 83     while(tt--)
 84     {
 85     //printf("Case %d: ",ca++);
 86         init();
 87     }*/
 88     getPrime();
 89     sum[0]=0;
 90     prime[0]=1;
 91     int c;
 92     while(scanf("%d%d",&n,&c)!=EOF&&n)
 93     {
 94         printf("%d %d:",n,c);
 95         init();
 96         int w=lower_bound(prime,prime+1229,n+1)-prime;
 97         //pt(w)
 98         if(w%2)
 99         {
100             int temp=c*2-1;
101             for(i=((w+1)/2)-c>=0?((w+1)/2)-c:0;i<w&&temp>0;i++,temp--)
102             {
103                 printf(" %d",prime[i]);
104             }
105         }
106         else
107         {
108             int temp=c*2;
109             for(i=(w/2)-c>=0?(w/2)-c:0;i<w&&temp>0;i++,temp--)
110             {
111                 printf(" %d",prime[i]);
112             }
113         }
114         ptn
115         ptn
116     }
117 }

View Code