SGU 117 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=117

117. Counting

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Find amount of numbers for given sequence of integer numbers such that after raising them to the M-th power they will be divided by K.

给出一系列数,统计出其中 M 次幂能被 K 整除的个数.

Input

Input consists of two lines. There are three integer numbers N, M, K (0

输入包含两行.第一行有三个整数 N, M, K (0

Output

Write answer for given task.

输出结果.

Sample Input

4 2 50
9 10 11 12

Sample Output

1

将 K 分解为 pri[1]^c[1]*pri[2]^c[2]*pri[3]^c[3]*pri[4]^c[4]......的形式,其中pri[1],pri[2].....为质因数
再将所给的数也做这样这样的分解,对比相应的系数即可.

CODE1

#include<stdio.h>
#include<string.h>
 
int main()
{
  int i,j;
  bool prime[100];
  memset(prime,true,sizeof(prime));
  for(i=2;i<100;++i)//筛法求素数
    if(prime[i]){
	for(j=i+i;j<100;j+=i)
	  prime[j]=false;
    }
  int pri[100],t;//存素数
  for(i=2,t=0;i<100;i++)
    if(prime[i]) pri[++t]=i;
 
  int n,m,k;
  int cnt=0,x,c[100];//数组c存指数
  scanf("%d%d%d",&n,&m,&k);
  memset(c,0,sizeof(c));
  for(j=t;j && k>1;)
    if(k%pri[j]==0){
	++c[j];
	k/=pri[j];
    }
    else
      --j;
  for(j=t;j;--j)
    if(c[j]){
	if(c[j]%m==0) c[j]/=m;
	else c[j]=c[j]/m+1;
	for(i=0;i<c[j];++i)
	  k*=pri[j];
    }
  while(n--){
      scanf("%d",&x);
      if(x%k==0) ++cnt;
  }
  printf("%dn",cnt);
  return 0;
}

CODE2

//code1暂时无法AC,还未查处错误
#include<stdio.h>
#include<string.h>
 
int main()
{
  int i,j;
  bool prime[100];
  memset(prime,true,sizeof(prime));
  for(i=2;i<100;++i)//筛法求素数
    if(prime[i]){
	for(j=i+i;j<100;j+=i)
	  prime[j]=false;
    }
  int pri[100],t;//存素数
  for(i=2,t=0;i<100;i++)
    if(prime[i]) pri[++t]=i;
 
  int n,m,k;
  int cnt=0,x,c1[100],c2[100];//数组c1,c2存指数
  scanf("%d%d%d",&n,&m,&k);
  memset(c1,0,sizeof(c1));
  for(j=t;j;)
    if(k%pri[j]==0){
	++c1[j];
	k/=pri[j];
    }
    else
      --j;
  while(n--){
      scanf("%d",&x);
      memset(c2,0,sizeof(c2));
      for(j=t;j;)
	if(x%pri[j]==0){
	    ++c2[j];
	    x/=pri[j];
	}
	else
	  --j;
      for(j=t;j;--j)
	if(m*c2[j]<c1[j] || x!=k) break;
      if(j==0) ++cnt;
  }
  printf("%dn",cnt);
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>