这一题的想法很巧妙,倒着想,不是找倍数而是更新约数,注意在求b[i],c[i]要在找a[i]的约数之前求解,为了避免1,a[i]都会被标记的情况,约数只要枚举到sqrt(a[i]),因为x,y和y,x是对称的。
这一题把a,b,c的long long改成int就木有再TLE了是神马情况。。。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> #include<map> #include<time.h> #include<bitset> using namespace std; //hdu 4961 const int maxn=1e5+10; int n; int a[maxn]; int b[maxn]; int c[maxn]; int d[maxn]; long long sum; int main() { freopen("input.txt","r",stdin); //freopen("data.txt","r",stdin); //freopen("out1.txt","w",stdout); //while(true) while(scanf("%d",&n)!=EOF) { // scanf("%d",&n); if(n==0) break; memset(d,0,sizeof(d)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); sum=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { if(d[a[i]]) { b[i]=a[d[a[i]]]; } else { b[i]=a[i]; } for(int x=1;x<(int)(sqrt(a[i]*1.0)+1);x++) { if(a[i]%x==0) { d[x]=i; d[a[i]/x]=i;// } } } memset(d,0,sizeof(d)); //c[n]=a[n]; for(int i=n;i>=1;i--) { if(d[a[i]]) { c[i]=a[d[a[i]]]; } else { c[i]=a[i]; } for(int x=1;x<(int) (sqrt(a[i]*1.0)+1);x++) { if(a[i]%x==0) { d[x]=i; d[a[i]/x]=i; } } } for(int i=1;i<=n;i++) { sum+=(long long)b[i]*c[i]; } printf("%I64d\n",sum); } return 0; }