Codeforces Round #226 (Div. 2) C题

数论好题

题目要求：求给定序列的素因子如果在给定区间内该数字个数加1;

思路：打表时求出包含给素数因子的数的个数，详见代码 1 #include<cstring>

 2 #include<algorithm>

 3 #include<cstdio>

 4 using namespace std;

 5 const int MAX=+;

 6 int vis[MAX],sum[MAX],num[MAX];

 7 int main()

 8 {

 9     int a,l,r,n,m;

     scanf("%d",&n);

     memset(vis,,sizeof(vis));

     memset(sum,,sizeof(sum));

     for(int i=;i<n;i++)

     {

         scanf("%d",&a);

         num[a]++;

     }

     for(int i=;i<MAX;i++)

     {

         if(!vis[i])

         {

             for(int j=i;j<=MAX;j+=i)

             {

                 vis[j]=;

                 sum[i]+=num[j];

             }

         }

         sum[i]+=sum[i-];

     }

     scanf("%d",&m);

     for(int i=;i<m;i++)

     {

         scanf("%d %d",&l,&r);

         l=min(l,MAX-);

         r=min(r,MAX-);

         printf("%d\n",sum[r]-sum[l-]);

     }

     return ;

39 }

巴特西

Codeforces Round #226 (Div. 2) C题

最新文章

热门文章