神奇的%系列一
Time Limit: 6000/3000 MS (Java/Others) Memory Limit:65536/32768 KB (Java/Others)
Problem Description
在计算机的世界里,%不是百分比,而是除法取余哟!
比如:
4 % 2 = 0
5 % 3 = 2
给你 2<=N<=100000 个数,a[1],a[2]...a[i]...a[n]。
其中:1<=a[i]<=100000。
问有几个组合 ( a[i] , a[j] ),(其中i!=j,且a[i]>a[j]),
使得 a[i] % a[j] != 0。
Input
输入有多组数据,对于每组数据:(T<=30)
第一行:N(表示N个数)
第二行:N个元素 a[i]
Output
输出有几个组合(a[i],a[j]),使得a[i] % a[j] != 0
Sample Input
3 1 1 1 4 1 2 3 4 5 1 2 2 4 6
Sample Output
0 2 1
#include<iostream> #include<cstdio> #include<cstring> #define M 100005 #define ll long long using namespace std; int main() { ll n; int i,j; ll a[M],b[M],max; ll s; while(~scanf("%d",&n)) { memset(b,0,sizeof b); for(i=0,max=0;i<n;i++) { scanf("%d",&a[i]); b[a[i]]++; if(a[i]>max) max=a[i]; } s=n*(n-1)/2;//先将所有组合算出来 for(i=1;i<=max;i++) { if(b[i])//枚举所有数找到反例 { for(j=i;j<=max;j+=i) { if(j==i) s-=b[j]*(b[j]-1)/2;//由于自身的的组合也是反例,特例处理 else s-=b[i]*b[j];//向后找b[i]的倍数,凑成反例组合 } } } printf("%lld\n",s); } return 0; }