首页 > 代码库 > hdu 4961 Boring Sum

hdu 4961 Boring Sum

2024-07-18 10:56:14   226人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4961

先打个表，把每个数的约数存起来，然后从前往后扫一遍，结果存在f[i],然后从后往前扫一遍，结果存在c[i],最后算f[i]*c[i]的和。

 1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #define maxn 100001 6 using namespace std; 7  8 int f[maxn],c[maxn]; 9 vector<int>g[maxn];10 int vis1[maxn],vis2[maxn];11 int a[maxn];12 void inti()13 {14     for(int i=2; i<=maxn; i++)15     {16         for(int j=i; j<=maxn; j+=i)17         {18             g[j].push_back(i);19         }20     }21 }22 int n;23 int main()24 {25     inti();26     while(scanf("%d",&n)!=EOF)27     {28         memset(vis1,0,sizeof(vis1));29         memset(vis2,0,sizeof(vis2));30         memset(f,0,sizeof(f));31         memset(c,0,sizeof(c));32         memset(a,0,sizeof(a));33         if(n==0) break;34         for(int i=1; i<=n; i++)35         {36             scanf("%d",&a[i]);37         }38         for(int i=1; i<=n; i++)39         {40             if(vis1[a[i]]==0) f[i]=a[i];41             else f[i]=vis1[a[i]];42             vis1[1]=a[i];43             for(int j=0; j<(int)g[a[i]].size(); j++)44             {45                 vis1[g[a[i]][j]]=a[i];46             }47         }48         for(int i=n; i>=1; i--)49         {50             if(vis2[a[i]]==0) c[i]=a[i];51             else c[i]=vis2[a[i]];52             vis2[1]=a[i];53             for(int j=0; j<(int)g[a[i]].size(); j++)54             {55                 vis2[g[a[i]][j]]=a[i];56             }57         }58         __int64 sum=0;59         for(int i=1; i<=n; i++)60         {61             sum+=(__int64)f[i]*(__int64)c[i];62         }63         printf("%I64d\n",sum);64     }65     return 0;66 }
View Code

 


联系
我们