1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 5 using namespace std; 6 7 int main() 8 { 9 int n,m,t,flag; 10 double a,b; 11 scanf("%d",&t); 12 while(t--) 13 { 14 flag=1; 15 scanf("%d%d",&n,&m); 16 a=(n-2)*180.0/n; 17 b=(m-2)*180.0/m; 18 for(int i=0;i<=6&&flag;i++) 19 { 20 for(int j=0;j<=6&&flag;j++) 21 { 22 if(i*a+j*b==360) 23 { 24 flag=0; 25 } 26 } 27 } 28 if(flag) 29 printf("No "); 30 else 31 printf("Yes "); 32 } 33 } 34 35
不妨令n≤mnleq mn≤m。 如果n>6n>6n>6，由于所有角都大于120度且小于180度，也就是说，两个角一定不够，而三个角一定过多。因此一定无解； 当n≤6nleq6n≤6时，如果n=3n=3n=3或n=4n=4n=4或n=6n=6n=6，那么显然只需要正nnn边形的角就可以了。如果n=5n=5n=5，则已经有一个108度的角。若这种角：不取，则显然仅当m=6m=6m=6时有解；取1个，则还差360−108=252360-108=252360−108=252（度），但是没有一个正mmm边形的内角的度数是252的约数；取2个，则还差360−108×2=144360-108 imes2=144360−108×2=144（度），这恰好是正10边形的内角，取3个，则还差360−108×3=36360-108 imes3=36360−108×3=36（度），也不可能满足；取大于3个也显然不可能。 因此得到结论：当nnn和mmm中至少有一个为3或4或6时，或者当nnn和mmm中一个等于5另一个等于10时，有解，否则无解，时间复杂度为O(T)Oleft(T ight)O(T)。