2019.7.8 校内测试题 牛数

校内测试题 牛数"/>

2019.7.8 校内测试题 牛数

　题目

牛数(cow.cpp,1s,128MB)

【问题描述】:

我们下面来研究整数性质，我们知道质数只有 1 和自身两个因子，合数至少 有除了 1 和自身的其他因子，我们也知道“猫老大数”是只能分解成两个质数乘 积形式的数，那么能分解成两个合数的数呢？我们称之为“牛数”。下面编程判 断整数是否为“牛数”。

【输入文件】:

　　 第一行为 t(1≤t≤1000)，表示测试数据组数。

接下来 t 行，每行一个正整数 x。

【输出文件】:

　　对于每个输入数据 x，判断它是否为“牛数”，并输出一行字符串：如果它

是“牛数”，输出“cow”，否则输出“no”。

【输入输出样例】：

cow.in 2 15 36 cow.out no cow

【数据规模】:

　　60%的数据：1≤x≤10^9

100%的数据：1≤x≤10^12

 

 

考试得分：　　0

 

 

主要算法 ：　　质数（质因数分解）

 

 

 

题干：

　　　　质因数分解板子

 

 

应试策略：

　　筛选出质数，尽量减小时间复杂度，然后模拟

　　 代码

 

#include<map>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,10000,stdin),pa==pb)?EOF:*pa++
#define File(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)using namespace std;
static char buf[10000],*pa=buf,*pb=buf;
inline int read();const int T=1000,N=1000000;
int Maxn,n,t[T+1],prime[N+1],v[N+1],cnt;map<int,bool> mp;
bool Solve(int tt)
{FORa(i,2,sqrt(tt)){if(tt%i==0&&!mp[i]){int p=tt/i;FORa(j,2,sqrt(p)) if(p%j==0) return 1;    }}return 0;
}
int main()
{File("cow");n=read();FORa(i,1,n) t[i]=read(),Maxn=Maxn>t[i]?Maxn:t[i];FORa(i,2,Maxn){if(!v[i]) v[i]=i,prime[++cnt]=i;FORa(j,1,cnt){if(prime[j]>v[i]||prime[j]*i>Maxn) break;v[prime[j]*i]=prime[j];}}FORa(i,1,cnt) mp[prime[i]]=1;FORa(i,1,n) Solve(t[i])?printf("cow\n"):printf("no\n");return 0;
}
inline int read()
{register int x(0);register int f(1);register char c(gc);while(c<'0'||c>'9') f=c=='-'?-1:1,c=gc;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc;return x*f;
}

 

 

 

 

 

非完美算法：　　

　　　　照搬应试策略

 

 

正解：

　　质因数个数判定

　　代码

　　

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define LL long long
#define FORa(i,s,e) for(LL i=s;i<=e;i++)
#define FORs(i,s,e) for(LL i=s;i>=e;i--)
#define gc getchar()//pa==pb&&(pb=(pa=buf)+fread(buf,1,10000,stdin),pa==pb)?EOF:*pa++
#define File(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)using namespace std;
static char buf[10000],*pa=buf,*pb=buf;
inline LL read();LL n,t,ans;int main()
{File("cow");n=read();FORa(i,1,n){t=read(),ans=0;FORa(j,2,sqrt(t)) {while(t%j==0) {    t/=j,ans++;        if(ans>=4) break;}    if(ans>=4) break;}if(t>1) ans++;(ans>=4)?printf("cow\n"):printf("no\n"); } return 0;
}
inline LL read()
{register LL x(0);register LL f(1);register char c(gc);while(c<'0'||c>'9') f=c=='-'?-1:1,c=gc;while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc;return x*f;
}

 

 

 

 

总结：

　　1.注意最后除完的数是否是一个质数
　　2.江湖救急算法

 

 

 

 

 

 

转载于:.html