等式數(shù)量 Time Limit:1000MS?????Memory Limit:32768KB?????64bit IO Format:%I64d & %I64u Submit?Status?Practice?FZU 1707

Description

?

集合是基本的數(shù)學(xué)概念，它是集合論的研究對(duì)象。關(guān)于集合論最簡(jiǎn)單的說(shuō)法，是在最原始的集合論《樸素集合論》中的定義：集合就是“一堆東西”。集合里的“東西”，叫作元素。若x是集合A中的元素，記作 x∈A。集合中的元素是互不相同的。?
表示相等關(guān)系的式子叫做等式。?
給你一個(gè)包含有N個(gè)整數(shù)的集合，如果從集合中找到三個(gè)不同的整數(shù)a,b,c使得a+b=c，那么我們說(shuō)這個(gè)集合包含一個(gè)等式。?
你的任務(wù)是從集合中找出所有的等式數(shù)量。?

?

Input

每組輸入數(shù)據(jù)的第一行為一個(gè)整數(shù)N (3<=N<=5,000)，表示集合中一共有N個(gè)不同的整數(shù)。之后一行有N個(gè)整數(shù)，表示集合中的元素，元素的整數(shù)值大小為(-10,000,000~10,000,000)。

Output

對(duì)于每組數(shù)據(jù)輸出一個(gè)整數(shù)占一行，表示該集合的等式數(shù)量。

Sample Input

4 3 1 2 5

Sample Output

2

#include<stdio.h> #include<string.h> #define N 50050 int s[N]={0},a[N],vis[N]; int hash(int x) {int y=(x%N+N)%N;while(vis[y]&&s[y]!=x)y=(y+1)%N;return y; } int insert(int x) {int y=hash(x);vis[y]=1;s[y]=x; } int find(int x) {return vis[hash(x)]; } int main() {int n,i,j;while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));for(i=0;i<n;i++){scanf("%d",&a[i]);insert(a[i]);}int sum=0;for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(a[i]&&a[j]&&find(a[i]+a[j])==1)sum++;}}printf("%d\n",sum);} }

總結(jié)

以上是生活随笔為你收集整理的等式数量--hash算法之除留余数法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。