题目
牛数(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.江湖救急算法
