首页 > 代码库 > hdu4961 Boring Sum
hdu4961 Boring Sum
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; const int maxn=100010; vector<int> v[maxn]; int a[maxn],b[maxn],s[maxn],h[maxn]; int main() { int i,j,n; for(i=1;i<maxn;i++)//预处理每个数的约数 注意这里不能取等 不然超了 for(j=i;j<maxn;j+=i) v[j].push_back(i); while(~scanf("%d",&n)&&n) { for(i=1;i<=n;i++) scanf("%d",s+i); memset(h,-1,sizeof h); for(i=1;i<=n;i++) { if(h[s[i]]!=-1) b[i]=s[h[s[i]]]; else b[i]=s[i]; for(j=0;j<v[s[i]].size();j++) h[v[s[i]][j]]=i; } memset(h,-1,sizeof h); for(i=n;i>0;i--) { if(h[s[i]]!=-1) a[i]=s[h[s[i]]]; else a[i]=s[i]; for(j=0;j<v[s[i]].size();j++) h[v[s[i]][j]]=i; } ll ans=0; for(i=1;i<=n;i++) ans+=(ll)a[i]*b[i]; cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。