SGU113~121

时间：2010-12-29 来源：LitIce

114：让你建“邮局”，求中位数，经典问题。

115: 模拟日历，直接模拟。

116：将求出的“下标素数”做完全背包，然后输出路径即可。

117: 让你判断给出的数a^m % k是否等于零，分解质因数即可，时间有点紧，注意常数。

118：数位和函数设为f(x);试几个小数发现f(x+y)=f(f(x)+f(y)) f(x*y)=f(f(x)*f(y))这样就可以A掉了。网上有人数直接是对9取模！不懂证明，强大的性质：数位和等价于将该数mod 9；

119:　A0*x+B0*y=n*t1 求（A,B）使得Ax+By=n*t2.先将消元得到(A*B0-A0*B)*x=n*t3;于是A*B0和A0*B关于n同余这时就可以有个想法，解出A*B0 mod n=k && A0*B mod n=k {K1}和{K2} |K1|*|K2|就是一些解……

如果（B0，n）！=1那么|K1|<n

同样（A0，n）！=1那么|K2|<n

也就是说出现了重复！

令d=gcd(gcd(a,b),n);a/=d;b/=d;n/=d;

这样处理之后（a,n)=1 和 (b,n)=1二者必居其一，此时二元积不会出现重复！

不妨假设（a,n)=1那么k*a mod n={0,1,2,...n-1}

{|H0|，|H1|，|H2|……|Hn-1|}

Hi表示（k*b mod n=i)的个数。

此时显然|H0|+|H1|+|H2|+...+|Hn-1|=n.

回想一下如果令A=i*A0;B=i*B0这时也得到了n组且互异的n组（因为（a,n)=1)。到此，n组都被找出来了。

120：

先求出圆心，然后通过O和起点，不断地顺时针旋转得出其他点。

　　　　　读入B和C我们可以先有题目给的下标求出 theta=“角BFA” 通过BA/sin theta求出r

　　　　　圆心的球法不必要解方程,根据三角形AEF与三角形BCD相似得出A和F的关系式。

代码

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <iostream>

#define dis(a,b)(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)))

using namespace std;

struct Tnode{
       double x,y;
       } N1,N2,O,st,ss;

double theta,r;
const double pi=acos(0.)*2;
int  n,a,b;
int main()
{
    freopen("120.in","r",stdin);
    freopen("120.out","w",stdout);
    cin>>n>>a>>b;
    
    cin>>N1.x>>N1.y>>N2.x>>N2.y;
    if (b<a) swap(a,b),swap(N1,N2);
    
    r=dis(N1,N2)/sin(pi*abs(b-a)/n)/2;
    
    O.x=(N1.x+N2.x)/2;
    O.y=(N1.y+N2.y)/2;
    O.x+=(N2.y-N1.y)/tan(pi*abs(b-a)/n)/2;
    O.y-=(N2.x-N1.x)/tan(pi*abs(b-a)/n)/2;
   //    printf("*%.6lf %.6lf\n",O.x,O.y);
    st.x=N1.x-O.x;st.y=N1.y-O.y;
    
    for (int i=1;i<=n;++i)
    {
        theta=-pi*2*(i-a)/n;
        ss.x=st.x*cos (theta)-st.y*sin (theta);
        ss.y=st.y*cos (theta)+st.x*sin (theta);
        
        printf("%.6lf %.6lf\n",O.x+ss.x,O.y+ss.y);
    }
    return 0;
}