4483: 「2018 集训队互测 Day 3」蒜头的奖杯
内存限制：1024 MB
时间限制：2.500 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
蒜头是一个热爱学习的好孩子。同时，他也是一名国家队选手。
作为新时代的社会主义优秀青年，每年冬天，蒜头都会和他的小伙伴们一起参加志愿者活动。今年的活动地点在步行街附近，于是蘑菇头提出，志愿者活动结束后去步行街逛一逛。 恰巧这一天步行街举办知识竞赛，冠军奖品是一瓶洗手液和一个金灿灿的奖杯，为了争夺这个奖杯，场上两支队伍的队员都使出浑身解数，直到最后一题，比赛的结局仍充满悬念。但在专业的最后一题面前，两支队伍的选手尽管绞尽脑汁，也没能取得丝毫进展。 蒜头看着屏幕上的问题皱起了眉头： **给定长度为 $ n $ 的六个序列 $ A,B,C,D,E,F $ ，求：** $$ \sum_{i = 1}^n \sum_{j = 1}^n \sum_{k = 1}^n A_i B_j C_k D_{\gcd(i,j)} E_{\gcd(i,k)} F_{\gcd(j,k)} $$ 你能帮蒜头解决这道难题吗？这样他就可以上台击败两队，赢得 Toms Chen 的金奖杯和一瓶优秀的洗手液了。当然，你为蒜头解决问题也不是无偿的：赢得了这瓶洗手液后蘑菇头会很开心，蒜头也会很开心，获得了金奖杯他会更开心，于是他就会奖励你 $ 100 $ 分了。 由于答案太大，你只要输出其对 $ 2^{64} $ 取模的结果即可。
作为新时代的社会主义优秀青年，每年冬天，蒜头都会和他的小伙伴们一起参加志愿者活动。今年的活动地点在步行街附近，于是蘑菇头提出，志愿者活动结束后去步行街逛一逛。 恰巧这一天步行街举办知识竞赛，冠军奖品是一瓶洗手液和一个金灿灿的奖杯，为了争夺这个奖杯，场上两支队伍的队员都使出浑身解数，直到最后一题，比赛的结局仍充满悬念。但在专业的最后一题面前，两支队伍的选手尽管绞尽脑汁，也没能取得丝毫进展。 蒜头看着屏幕上的问题皱起了眉头： **给定长度为 $ n $ 的六个序列 $ A,B,C,D,E,F $ ，求：** $$ \sum_{i = 1}^n \sum_{j = 1}^n \sum_{k = 1}^n A_i B_j C_k D_{\gcd(i,j)} E_{\gcd(i,k)} F_{\gcd(j,k)} $$ 你能帮蒜头解决这道难题吗？这样他就可以上台击败两队，赢得 Toms Chen 的金奖杯和一瓶优秀的洗手液了。当然，你为蒜头解决问题也不是无偿的：赢得了这瓶洗手液后蘑菇头会很开心，蒜头也会很开心，获得了金奖杯他会更开心，于是他就会奖励你 $ 100 $ 分了。 由于答案太大，你只要输出其对 $ 2^{64} $ 取模的结果即可。
输入
第一行输入一个正整数 $ n $ 。
接下来 $ 6 $ 行，每行 $ n $ 个非负整数，分别表示序列 $ A, B, C, D, E, F $。
输出
输出一行一个整数，表示上式的值对 $ 2^{64} $ 取模的结果。
样例输入 复制
3
1 0 0
1 0 0
1 0 0
1 0 0
1 0 0
1 0 0样例输出 复制
1提示
输入样例2
3 5 2 6 2 0 5 5 9 2 2 2 9 8 4 9 2 6 4
输出样例2
111472
输入样例3
10 1361955 7579012 28145516 76140462 83515280 86969585 62888635 26402539 98152102 58176572 61402892 27860889 9580638 70870044 46139319 78509022 84027666 61263304 41082555 58212774 40563715 26389629 79113528 96147999 25801172 37151740 70301173 56585275 85845005 2071050 3573723 27123762 9467290 96231662 31265400 99374333 20690249 98571510 91747709 99313372 43215695 89204466 14608448 62733264 56517316 55253431 6956091 81457954 28156706 51354013 58398859 52040410 43974602 58000642 37883250 64556873 82264704 5461189 77444309 67035008
输出样例3
3310381507991040368
数据范围：对于所有数据，$ n \le 10^5 $ ，输入序列中的数字不会超过 $ 10^{18} $ 。 | 测试点编号 $ m $ | $ n \le $ | 其他约定 | | :-------------: | :---------------------: | :--------------------------------------: | | $ 1 $ | $ 100 $ | - | | $ 2,3,4 $ | $ 2000 $ | - | | $5,6$ | $ 10^5 $ | $ D_i = [i = 1], E_i = F_i = 1 $ | | $7$ | $ 10^5 $ | $ A_i = B_i = C_i = D_i = 1, E_i = F_i = [i = 1] $ | | $8$ | $ 10^5 $ | $ D_i = 1, E_i = F_i = [i = 1] $ | | $9,10$ | $ 10^5 $ | $ A_i = B_i = C_i = 1, D_i = E_i = F_i = [i = 1] $ | | $11,12,13$ | $(m - 3) \times 10^4$ | $ D_i = E_i = F_i = [i = 1] $ | | $14 \ldots 20$ | $ (m-13) \times 10^4 $ | 当 $ m $ 为奇数时，有 $ D_i = E_i = F_i = i $ | | $ 21\ldots 25 $ | $ 5(m - 5) \times 10^3$ | 当 $ m $ 为偶数时，有 $ D_i = E_i = F_i = i $ |