##思路 1：純暴力！！！–>40分
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int N=1e5+100,mod=1000007;
int ans;
int gcd (int a,int b)
{
if (b==0) return a;
return gcd (b,a%b);
}
int main ()
{
for (int n=1;n<=1000;n++)
{
ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
ans+=gcd (gcd (i,j),k);
printf ("%d ",ans);
}
return 0;
}
有手就行 O(∩_∩)O 哈哈
思路2：暴力+優化！！！
我們可以發現：對于n，它應該等于n-1的所有“ans”+三個數中有一個數是“n”的“ans”
那我們就又可以得出：i循環是沒有用的，因為我們可以将“i”一直當做“n”，然後我們
就隻用枚舉“j”，“k”,的可能性，再将“n”分别放入“j”,“k”前中後3個的位置上,再注意一下
即可…貌似我自己都沒看懂…去看代碼吧…
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int N=1e5+100,mod=1000007;
int ans,m;
int gcd (int a,int b)
{
if (b==0) return a;
return gcd (b,a%b);
}
int main ()
{
scanf ("%d",&m);
for (int n=1;n<=m;n++)
{
for (int j=1;j<=n;j++)
{
for (int k=j;k<=n;k++)
{
int sb=gcd (n,gcd (j,k)),num=0;
if (n==j) num++;
if (n==k) num++;
if (num==2) ans+=n;
else if (num==1) ans+=(sb*3);
else
{
if (k==j) ans+=(sb*3);
else ans+=(sb*6);
}
}
}
}
printf ("%d",ans);
return 0;
}
而…
真正的解法：--------------------------------->打表！！！
先看資料–>
OK
則我們用一個f數組放，當n==i是的解
先用上面的代碼輸出，再存入新代碼
代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
#define LL long long
using namespace std;
const LL N=1e5+100;
LL n,a[N]={0,1,9,30,76,141,267,400,624,885,1249,1590,2208,2689,3411,4248,5248,6081,7485,8530,10248,11889,13687,15228,17988,20053,22569,25242,28588,31053,35463,38284,42540,46581,50893,55362,61824,65857,71247,76884,84388,89349,97881,103342,111528,120141,128047,134580,146316,154177,164817,174438,185836,194157,207927,218812,233268,245277,257857,268182,288216,299257,313635,330204,347836,362973,383709,397042,416448,434025,456967,471948,499740,515581,536073,559758,583960,604833,633651,652216,683712,709065,734233,754734,793188,818917,846603,874512,909496,933081,977145,1006126,1041504,1073385,1106467,1138536,1187112,1215145,1255101,1295142,1342852,1373253,1422195,1453816,1502376,1553361,1595437,1629570,1691292,1726717,1782111,1827492,1887772,1925853,1986837,2033674,2089776,2145333,2197483,2246640,2332104,2379085,2434833,2490534,2554600,2609625,2693919,2742052,2813988,2875245,2952085,3003306,3096024,3157249,3224511,3306240,3388576,3444609,3533637,3591322,3693924,3767085,3842623,3912324,4027884,4102093,4181949,4270422,4361548,4427853,4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692,10962213,11115121,11256486,11474160,11621905,11780931,11951868,12152644,12299469,12557589,12690730,12877248,13044009,13215631,13378068,13639212,13800565,13978665,14154942,14401360,14564721,14793483,14942224,15188880,15419685,15611101,15765234,16036176,16193041,16429311,16663212,16899868,17062269,17342853,17536762,17767764,17974173,18222175,18393060,18746652,18920413,19157001,19390038,19636924,19871697,20152263,20355532,20625636,20853453,21130753,21319254,21694104,21908065,22149867,22437552,22728496,22926129,23234577,23463814,23805108,24075513,24332791,24539772,24931452,25177789,25486401,25748310,26046016,26262561,26675175,26894956,27234516,27558429,27839821,28128786,28523688,28753321,29042991,29351592,29785072,30021393,30389565,30629266,30963492,31321485,31672711,31953804,32425836,32688877,33062565,33373626,33726904,33983865,34429779,34734808,35118504,35492157,35825017,36121134,36654504,36963505,37305363,37642584,38065072,38391057,38865501,39147634,39616920,39967617,40394071,40683612,41225940,41519221,41888793,42384162,42797764,43098597,43566255,43904500,44429652,44808093,45257725,45601170,46169952,46569937,46968303,47361012,47831476,48200253,48818913,49146934,49603392,50041701,50459863,50852892,51526308,51866341,52323525,52745562,53322544,53708505,54298779,54698668,55215828,55737405,56186161,56546694,57171096,57535801,58143171,58660356,59251012,59624133,60203157,60644362,61169064,61716561,62196991,62582916,63412356,63821065,64312293,64834254,65483848,65950185,66568971,66972304,67587720,68125101,68730733,69199074,69911592,70328233,70921695,71533620,72150796,72618765,73404141,73834306,74552100,75085101,75632119,76071420,76872060,77491909,78050445,78641142,79264228,79717413,80573763,81073864,81821688,82388769,82970701,83516610,84414252,84886285,85480095,86161164,86992564,87474165,88220157,88754098,89429544,90180657,90891319,91439292,92355780,92856805,93599289,94219470,94921888,95501673,96361407,96963844,97781220,98419629,99157789,99683634,100827984,101358865,102026463,102731352,103515112,104190777,105028173,105647746,106405692,107180709,107996839,108553260,109628292,110189893,111000765,111825138,112611640,113233569,114118647,114695932,115733556,116587773,117408865,117996726,119008440,119700889,120446595,121180104,122179048,122782953,123944493,124616194,125461392,126214713,126987415,127845180,128985180,129610813,130397193,131270778,132316132,132952773,134129775,134771956,135744444,136685061,137499157,138152490,139394688,140141545,141115407,141929748,142899964,143638245,144674289,145514614,146611944,147507021,148363591,149050956,150490956,151248877,152119845,153111618,154157344,154979553,156150327,156860860,157897644,158775381,159955693,160677954,161918172,162708157,163729311,164914584,166024144,166862457,168005745,168751750,169977900,170899221,171843979,172602000,174180024,175071289,176146005,177153882,178221148,178997373,180443943,181329964,182500908,183587361,184577833,185504670,186867852,187748725,188899827,189888504,191324248,192137529,193495953,194315494,195450960,196790985,197828251,198729504,200340360,201212221,202448781,203556726,204921484,205850445,207164499,208164568,209414304,210472713,211557853,212625654,214451880,215328841,216430179,217512360,218892616,219930345,221558841,222455374,223697100,224881041,226333231,227315508,228975396,230012461,231163113,232498398,233776600,234706233,236256087,237277084,239059956,240368637,241552765,242502546,244129080,245244217,246445263,247873212,249275956,250246101,252045201,253022182,254575080,255780081,257191003,258414288,260324016,261321649,262640985,263871342,265522876,266667237,268227459,269345800,270828360,272468205,273755641,274788174,276759864,277880449,279411027,280692888,282267808,283321569,285199149,286647586,288116088,289424097,290910535,291985740,294228660,295311061,296861793,298288842,299796988,301176993,302868219,303972352,305688768,307255497,308891041,310109142,312206772,313332853,314746275,316382952,318355768,319496601,321255309,322403554,324287772,325869297,327319795,328635000,330863472,332262097,333731313,335358702,336988948,338267925,340758567,341951788,343687044,345157485,346664497,348072486,350137608,351614461,353311911,354913632,357031264,358262625,360160257,361399318,363386052,365184909,366908491,368163024,370552848,371936953,373945653,375733074,377490172,378768093,380737167,382235092,384165372,385858209,387708361,389009886,391745940,393055381,394698459,396508512,398423272,400224465,402424209,403853638,405697944,407340321,409311643,410790624,413528256,414885697,416588889,418726074,420744376,422118009,424233927,425795404,428219484,429921285,431857753,433255854,435864360,437502409,439508175,441240084,443361580,444907917,447526917,448957978,450937056,453190125,454995907,456682056,459303936,460871329,462697989,464490906,467175676,468648477,471245499,472835584,475222176,477368361,479237137,480929670,483485652,484992277,487204851,489186156,491386732,493017333,495766617,497816014,499934616,501821025,503753875,505303320,508711584,510471625,512520357,514438458,516604624,518536449,521155395,522739528,525468336,527583165,529921585,531644166,534375384,535985785,538005747,540607836,543106012,544888485,547584489,549221374,551895516,554146149,556494931,558149592,561140712,563077801,565164357,567350574,569971720,571870737,574941987,576632488,579163488,581244009,583591273,585580638,589051812,590769445,592923675,595292232,598306528,600042369,602713821,604684306,607096212,609864441,612064387,613978056,617199432,618971977,622084809,624265950,626728588,628519629,631482663,633686428,636299004,638835621,641105041,643053606,646838160,648838681,651346923,653844396,656913364,659063733,661905789,663762322,666328008,668612145,671348983,673466364,677237076,679281877,681645609,684370206,686988208,688892241,692310819,694365736,697741896,700254381,702665989,704780250,708072024,710693569,713371215,715760724,718592548,720554373,724324761,726296302,729433800,731858961,734606803,736924440,740685936,742827385,745336185,748452354,751729672,753750153,756858015,758888356,761833116,765034101,767940913,769991046,773787624,775847689,778867539,781401240,784701688,787193709,790392813,792825442,796084464,798933477,801566467,803676552,808484712,810673081,813331269,815938650,818881636,821544309,825079203,827700316,830913252,833557869,836947789,839261250,842955768,845136889,848242911,851684952,854862208,857063841,860953389,863165314,866767188,869875869,872661847,874894428,879259356,881869693,884681589,887587722,891166888,893641233,897777183,900241444,903538260,906521049,909639373,912713298,916617900,918923533,921813903,924648660,928907596,931234317,935520837,937858138,941482752,944854665,947797951,950156484,954401052,957074149,960544617,963954150,967241128,969795633,973470747,976265056,980287968,983563113,986586673,989160678,994291668,996899989,1000267347,1003683840,1007226400,1010083425,1013857701,1016323834,1019729700,1022962761,1027267771,1029755712,1034432616,1037162737,1040295009,1043898006,1047364108,1050207861,1054590447,1057122292,1061509116,1064621157,1067808505,1070574126,1075773120,1078899985,1082115051,1085477028,1089421444,1092008709,1096726869,1099825006,1103413164,1106606805,1109877667,1113335976,1118550792,1121182825,1124926077,1128160914,1132457836,1135112397,1139192079,1142026900,1146002988,1150583457,1154284153,1156972686,1161542388,1164465205,1168679835,1171997856,1176602968,1179325689,1183812873,1186993918,1190769120,1194508809,1197949939,1201059576,1206875160,1209727501,1213526613,1217153982,1220992588,1224240525,1229215491,1232018824,1236404568,1240201857,1244321869,1247148450,1252315116,1255516021,1259073063,1263499548,1267748068,1270609701,1275006669,1278144034,1283354904,1287118749,1290734467,1293631368,1298833008,1302216817,1306176549,1310252226,1314758548,1317873885,1323822579,1326766840,1331266296,1334883777,1339084849,1342537638,1347579780,1350559813,1354294323,1358336628,1363480228};
int main ()
{
scanf ("%lld",&n);
printf ("%lld",a[n]);
return 0;
}