首页 > 代码库 > hdu 4961 数论 o(nlogn)
hdu 4961 数论 o(nlogn)
Boring Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 60 Accepted Submission(s): 30
Problem Description
Number theory is interesting, while this problem is boring.
Here is the problem. Given an integer sequence a1, a2, …, an, let S(i) = {j|1<=j<i, and aj is a multiple of ai}. If S(i) is not empty, let f(i) be the maximum integer in S(i); otherwise, f(i) = i. Now we define bi as af(i). Similarly, let T(i) = {j|i<j<=n, and aj is a multiple of ai}. If T(i) is not empty, let g(i) be the minimum integer in T(i); otherwise, g(i) = i. Now we define ci as ag(i). The boring sum of this sequence is defined as b1 * c1 + b2 * c2 + … + bn * cn.
Given an integer sequence, your task is to calculate its boring sum.
Here is the problem. Given an integer sequence a1, a2, …, an, let S(i) = {j|1<=j<i, and aj is a multiple of ai}. If S(i) is not empty, let f(i) be the maximum integer in S(i); otherwise, f(i) = i. Now we define bi as af(i). Similarly, let T(i) = {j|i<j<=n, and aj is a multiple of ai}. If T(i) is not empty, let g(i) be the minimum integer in T(i); otherwise, g(i) = i. Now we define ci as ag(i). The boring sum of this sequence is defined as b1 * c1 + b2 * c2 + … + bn * cn.
Given an integer sequence, your task is to calculate its boring sum.
Input
The input contains multiple test cases.
Each case consists of two lines. The first line contains an integer n (1<=n<=100000). The second line contains n integers a1, a2, …, an (1<= ai<=100000).
The input is terminated by n = 0.
Each case consists of two lines. The first line contains an integer n (1<=n<=100000). The second line contains n integers a1, a2, …, an (1<= ai<=100000).
The input is terminated by n = 0.
Output
Output the answer in a line.
Sample Input
51 4 2 3 90
Sample Output
136
Hint
In the sample, b1=1, c1=4, b2=4, c2=4, b3=4, c3=2, b4=3, c4=9, b5=9, c5=9, so b1 * c1 + b2 * c2 + … + b5 * c5 = 136.Source
2014 Multi-University Training Contest 9
Recommend
hujie | We have carefully selected several similar problems for you: 4970 4968 4967 4966 4965
题解:对于输入的数列,从前往后扫描一遍,对于每个数,都更新一下它的约数的左边最近倍数的值(b值);
同样地,从后往前扫描一遍,对于每个数,都更新一下它的约数的右边最近倍数的值(c值)。最后直接求所有b*c的和即可。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 10000511 #define M 1512 #define mod 100000000713 #define mod2 10000000014 #define ll long long15 #define maxi(a,b) (a)>(b)? (a) : (b)16 #define mini(a,b) (a)<(b)? (a) : (b)17 18 using namespace std;19 20 int n;21 ll a[N],b[N],c[N];22 int vis[N];23 ll ans;24 25 int main()26 {27 int i;28 // freopen("data.in","r",stdin);29 //scanf("%d",&T);30 //for(int cnt=1;cnt<=T;cnt++)31 //while(T--)32 while(scanf("%d",&n)!=EOF)33 {34 if(n==0) break;35 ans=0;36 memset(b,0,sizeof(b));37 memset(c,0,sizeof(c));38 memset(vis,0,sizeof(vis));39 for(i=1;i<=n;i++){40 scanf("%I64d",&a[i]);41 }42 43 vis[ a[1] ]=1;44 for(i=2;i<=n;i++){45 for(ll j=1;j*j<=a[i];j++){46 if(a[i]%j!=0) continue;47 if(vis[j]!=0){48 b[ vis[j] ]=a[i];49 vis[j]=0;50 }51 ll te=a[i]/j;52 if(vis[te]!=0){53 b[ vis[te] ]=a[i];54 vis[te]=0;55 }56 }57 vis[ a[i] ]=i;58 }59 60 61 for(i=1;i<=n;i++){62 if(b[i]==0) b[i]=a[i];63 }64 65 memset(vis,0,sizeof(vis));66 vis[ a[n] ]=n;67 for(i=n-1;i>=1;i--){68 for(ll j=1;j*j<=a[i];j++){69 if(a[i]%j!=0) continue;70 if(vis[j]!=0){71 c[ vis[j] ]=a[i];72 vis[j]=0;73 }74 ll te=a[i]/j;75 if(vis[te]!=0){76 c[ vis[te] ]=a[i];77 vis[te]=0;78 }79 }80 vis[ a[i] ]=i;81 }82 83 for(i=1;i<=n;i++){84 if(c[i]==0) c[i]=a[i];85 }86 87 for(i=1;i<=n;i++){88 ans+=b[i]*c[i];89 }90 printf("%I64d\n",ans);91 92 }93 94 return 0;95 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。