高速公路 (HIGHWAY,CERC 2006,LA 3720)

1 #include <iostream>
2 #include <string.h>
3 #include <string>
4 #include <fstream>
5 #include <algorithm>
6 #include <stdio.h>
7 #include <vector>
8 #include <queue>
9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const int INF=0x7fffffff;
14 unsigned long long uINF = ~0LL;
15 #define MAXN 10000007
16 typedef long long LL;
17 LL gcd(LL a,LL b)
18 {
19     return b==0?a:gcd(b,a%b);
20 }
21 int g[301][301];
22 void init()
23 {
24     for(int i=1;i<=300;i++)
25         for(int j=1;j<=300;j++)
26         g[i][j]=gcd(i,j);
27 }
28 int main()
29 {
30     int n,m;
31     init();
32     while(scanf("%d%d",&n,&m),n+m!=0)
33     {
34         LL ans=0;
35         n--;m--;
36         if(n>m)swap(n,m);
37
38         for(int i=1;i<=n;i++)
39             for(int j=i;j<=m;j++)
40             if(g[i][j]<=2)
41             {
42                 LL temp=(n-i+1)*(m-j+1);
43                 if(i==j)
44                 {
45                     if(g[i][j]==1)ans+=temp;
46                     else ans-=temp;
47                 }
48                 else
49                 {
50                     if(i<=m&&j<=n)temp+=(m-i+1)*(n-j+1);
51                     if(g[i][j]==1)ans+=temp;
52                     else ans-=temp;
53                 }
54             }
55             ans*=2;
56         printf("%lld\n",ans);
57     }
58
59     return 0;
60 }

(1 #include <iostream>
2 #include <string. h>
3 #include <string>
4 #include <fstream>
5 #include <algorithm>
6 #include <stdio. h>
7 #include <vector>
8 #include <queue>
9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const int INF=0x7fffffff;
14 unsigned long long uINF = ~0LL;
15 #define MAXN 10000007
16 typedef long long LL;
17 LL gcd(LL a,LL b)
18 {
19     return b==0? a:gcd(b,a%b);
20 }
21 int g[301][301];
22 void init()
23 {
24     for(int i=1;i<=300;i++)
25         for(int j=1;j<=300;j++)
26         g[i][j]=gcd(i,j);
27 }
28 int main()
29 {
30     int n,m;
31     init();
32     while(scanf("%d%d",&n,&m),n+m!= 0)
33     {
34         LL ans=0;
35         n--; m--;
36         if(n>m)swap(n,m);
thirty-seven
38         for(int i=1;i<=n;i++)
39             for(int j=i;j<=m;j++)
40             if(g[i][j]<=2)
41             {
42                 LL temp=(n-i+1)*(m-j+1);
43                 if(i==j)
44                 {
45                     if(g[i][j]==1)ans+=temp;
46                     else ans-=temp;
47                 }
48                 else
49                 {
50                     if(i<=m&&j<=n)temp+=(m-i+1)*(n-j+1);
51                     if(g[i][j]==1)ans+=temp;
52                     else ans-=temp;
53                 }
54             }
55             ans*=2;
56         printf("%lld\n",ans);
57     }
fifty-eight
59     return 0;
60 }
)