A 找一找
链接：https://www.nowcoder.net/acm/contest/71/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数
输入描述:
第一行输入一个n
接下来一行输入n个正整数ai
输出描述:
输出符合条件个数
示例1
输入
5
1 2 3 4 5
输出
2
说明
5个数中1和2符合条件，1是后面每个数的因子，2是4的因子
备注:
1≤n,ai≤1000000
暴力，也叫做筛法 和素筛的原理一样，但是时间复杂度 我还真估计不好，总感觉这个题这么写不就是暴力，最后无可奈何交了发，过了。
代码
#include<bits/stdc++.h>
using namespace std;
#define LL long longconst int N =1000000+11;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int M = 1e6;int a[N];
int cnt[N];
set<int>S;
set<int>::iterator it;
int main(){int n;scanf("%d",&n);int mx=0;for(int i=1;i<=n;i++) {scanf("%d",&a[i]);cnt[a[i]]++;S.insert(a[i]);mx=max(mx,a[i]);}int ans=0;for(it=S.begin();it!=S.end();it++){int u=*it;for(int j=u*2;j<=mx;j+=u){if(cnt[j]) {ans+=cnt[u];break;}}}cout<<ans<<endl;
return 0;
}
void init(){ //做了个实验这样遍历其所有倍数 时间复杂度差不多就是O（nlogn）的 .LL cnt=0;for(int i=1;i<N;i++) {for(int j=i;j<N;j+=i){cnt++;}}cout<<cnt<<endl;
}B 数一数
链接：https://www.nowcoder.net/acm/contest/71/B
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
设s,t为两个字符串，定义f(s,t) = t的子串中，与s相等的串的个数。如f(“ac”,”acacac”)=3, f(“bab”,”babab”)=2。现在给出n个字符串，第i个字符串为si。你需要对，求出，由于答案很大，你只需要输出对 998244353取模后的结果。
输入描述:
第一行一个整数n。
接下来n行每行一个仅由英文字母构成的非空字符串，第i个字符串代表si。
输出描述:
共n行，第i行输出对 998244353取模的结果。
示例1
输入
1
BALDRSKYKirishimaRain
输出
1
备注:
1 ≤ n ≤ 106，所有字符串的总长度不超过2*106
分析： 可以知道 对于不是最短的串来说，他的答案一定为0。所以我们只要单独求最短串就行了，但是最短串不一定就是一个，对于多个最短串来说（假设只有两个），他们肯定只有相等和不相等两种情况，如果相等那么 两者最后的答案一定一样，如果不相等 随便跑其中的一个串的匹配答案一定为0 .
综上 我们只需要任意找一个最短串来做一次匹配就好了。匹配次数用kmp就ok。
代码
#include<bits/stdc++.h>
using namespace std;
#define LL long longconst int N =1e6+11;
const int M = 2e6+11;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;string s[N];
int NEXT[M];
void pre(string x,int m){int i,j;j=NEXT[0]=-1;i=0;while(i<m){while(-1!=j&&x[i]!=x[j]) j=NEXT[j];if(x[++i]==x[++j]) NEXT[i]=NEXT[j];else NEXT[i]=j;}
}
LL KMP(string x,string y){int m=x.size(); int n=y.size();// pre(x,m);LL ans=0;int i,j; i=j=0;while(i<n){while(-1!=j&&y[i]!=x[j]) j =NEXT[j];i++;j++;if(j>=m){ans++;j=NEXT[j];}}return ans;
}LL solve(int i,int n){LL ans=1;pre(s[i],s[i].size());for(int j=1;j<=n;j++){if(i==j) continue;LL temp=KMP(s[i],s[j]);if(!temp) return 0;ans=(ans*temp)%mod;}return ans;
}
char ss[M];
int main(){int n; scanf("%d",&n);int t=inf,pos=-1;for(int i=1;i<=n;i++){scanf("%s",ss);s[i]=string(ss);if(s[i].size()<t){pos=i;t=s[i].size();}}LL ans=solve(pos,n);for(int i=1;i<=n;i++){if(t!=s[i].size()) puts("0");else {// cout<<i<<endl;printf("%lld\n",ans);}}
return 0;
}C 列一列
链接：https://www.nowcoder.net/acm/contest/71/C
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小W在计算一个数列{An},其中A1=1,A2=2,An+2=An+1+An。尽管他计算非常精准，但很快他就弄混了自己的草稿纸，他找出了一些他计算的结果，但他忘记了这些都是数列中的第几项。
输入描述:
每行包括数列中的一项Ak(k<=100000)。
总行数T<=30。
输出描述:
对于每一项Ak，输出一行包括一个正整数k表示输入中数是数列的第几项。
示例1
输入
2
3
5
8
13
输出
2
3
4
5
6
分析：怎么说，突然有的想法，100000的项值肯定是天文数字，肯定是记录不下来，但是仔细想一下，这个题目关键的就是对应而已，一个项对应一个值，一个值对应一个项，但是完全记录值来作对应肯定是不行，我们可以用一种对应法则来处理，比如我们只取每一项值的取mod后的值来当做这个关键字来对应，你可能会担心有的值会冲突（有是肯定会有的，但是根据你取的不同，这个冲突的概率是可以减少的），其实这里就是HASH的关键了（有兴趣可以百度看看hash有好多种方法处理冲突），而最简单的我们可以取多个mod，还好这个题目 1e9+7可以过。
代码
#include<bits/stdc++.h>
using namespace std;
#define LL long longconst int N =100000+11;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int M = 1e6;int f[N]={
0,1,2,3,5};
map<int,int>point;
void init(){point[1]=1,point[2]=2;for(int i=3;i<N;i++){f[i]=(f[i-1]+f[i-2])%mod;point[f[i]]=i;}
}
int main(){init();string s;while(cin>>s){int ans=0;for(int i=0;s[i];i++){ans=(ans*10ll+s[i]-'0')%mod;}cout<<point[ans]<<endl;}
return 0;
}
代码二
直接利用int的上界来hash
#include<bits/stdc++.h>
using namespace std;
#define LL long longconst int N =100000+11;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int M = 1e6;LL f[N]={
0,1,2,3,5};
int main(){for(int i=3;i<N;i++)f[i]=f[i-1]+f[i-2]; string s;while(cin>>s){LL ans=0;for(int i=0;s[i];i++) ans=(ans*10+s[i]-'0');for(int i=0;i<N;i++){if(f[i]==ans) {cout<<i<<endl;break;}}}
return 0;
}
手写一个hash，询问较多时候 效果明显一些。
#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long longconst int N = 100000+3;
const int MAXM = 1e6;
const int mod = 7651;
const int inf = 0x3f3f3f3f;struct HASH{ULL hs; // 存储关键字， 注意这里一定要是无符号类型的，否则会数组越界int id,next;
}MAP[N+3];// 插入关键字的总数
int head[mod],top;
void init(){memset(head,-1,sizeof(head));top=1;
}
void Insert(ULL a,int b){int c=a%mod;MAP[top].hs=a; MAP[top].id=b; MAP[top].next=head[c];head[c]=top++;
}
int Find(ULL x){int c=x%mod;for(int i=head[c];i!=-1;i=MAP[i].next){HASH h=MAP[i];if(h.hs==x) return h.id;}return -1;
}ULL f[N]={
0,1,2,3,5};
int main(){init();Insert(1ull,1);Insert(2ull,2);for(int i=3;i<N;i++){f[i]=f[i-1]+f[i-2];Insert(f[i],i);}string s;while(cin>>s){ULL ans=0;for(int i=0;s[i];i++) ans=ans*10+s[i]-'0';printf("%d\n",Find(ans));}return 0;
}