ACM STEPS——Chapter Two——Section One

数学题小关，做得很悲剧，有几道题要查数学书。。。

记下几道有价值的题吧

The area(hdoj 1071)

http://acm.hdu.edu.cn/showproblem.php?pid=1071

直线方程易求，曲线方程要推公式。。。设y=a*x^2+b*x+c,则顶点坐标为(-b/(2a),4ac-b^2)/(4a)),又从题目中已知顶点坐标为(x1,y1)，以及另一点(x2,y2)，则有

y2=a*x2*x2+b*x2+c

y1=a*x1*x1+b*x1+c

x1=-b/(2*a)

所以a=(y2-y1)/((x2-x1)*(x2-x1))

求出a后，剩下的b和c就没问题，而面积直接用定积分的定义搞定

AC CODE:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

int MIN(int a,int b) { if( a<b ) return a; else return b; }
int MAX(int a,int b) { if( a>b ) return a; else return b; }
#define CLR(NAME,VALUE) memset(NAME,VALUE,sizeof(NAME))

using namespace std;

const int N=10000;

int main() {
int ca,i;
double x1,y1,x2,y2,x3,y3,m,n,res,dtmp,x,a,b,c;
cin>>ca;
while( ca-- ) {
cin>>x1>>y1>>x2>>y2>>x3>>y3;

   //y=m*x+n
   m=(y2-y3)/(x2-x3);
   n=y3-m*x3;

   //y=a*x^2+b*x+c
   a=(y2-y1)/((x2-x1)*(x2-x1));
   b=-2*a*x1;
   c=y1-a*x1*x1-b*x1;

   x=x2;
   res=0;
      dtmp=(x3-x2)/N;
   for(i=0;i<N;++i) {
    x+=dtmp;
    res+=dtmp*(a*x*x+b*x+c-m*x-n);
   }

   printf("%.2lf ",res);
}

     return 0;
}

找新朋友（hdoj 1286)

http://acm.hdu.edu.cn/showproblem.php?pid=1286

定义：设φ(m)表示不超过m,而和m互质的正整数的个数，则φ(m)称为欧拉函数

计算公式：若a=（p1^a1）*（p2^a2）…（pn^an）是 a 的标准分解式,则

φ(a)= a*(1-1/p1)*(1-1/p2)…(1-1/pn) //pi是质数，且是a的因数

然后先求出范围内的质数，代公式，搞定

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

int MIN(int a,int b) { if( a<b ) return a; else return b; }
int MAX(int a,int b) { if( a>b ) return a; else return b; }
#define CLR(NAME,VALUE) memset(NAME,VALUE,sizeof(NAME))

using namespace std;

const int N=32768+2;
bool notPrim[N];

int main() {
int ca,n,i,j;
for(i=2;i<N;++i) {
   if( !notPrim[i] ) {
    for(j=i;i*j<N;++j) {
     notPrim[i*j]=true;
    }
   }
}

cin>>ca;
while( ca-- ) {
   cin>>n;
   double res=n;
   for(i=2;i<=n;++i) {
    if( !notPrim[i] && n%i==0 ) {
     res=res*(1-1.0/i);
    }
   }

   cout<<res<<endl;
}

     return 0;
}

整数对(hdoj 1271)

http://acm.hdu.edu.cn/showproblem.php?pid=1271

这个其实可以当作是一类题来处理，即去掉数字中一位数后，再OOXX的题

假设A是原来的数，B是去掉A中一位数后的数，N=A+B

A=a*10^(k+1)+b*10^k+c //假设要去掉的是第k+1位数,而b就是该位的数字，a是b之前的数字,c是b之后的数字

B=a*10^k+c

N=a*11*10^k+b*10^k+2*c

从枚举10^k入手，将第三式右边除以10^k后，得到a*11+b，那么要得到a，只需再除以11,而要b，则对11取余。但这只是2*c无进位的情况，当有进位时，要将得到的b的值再减1。再下来就是验证c是否存在就可以了。

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

int MIN(int a,int b) { if( a<b ) return a; else return b; }
int MAX(int a,int b) { if( a>b ) return a; else return b; }
#define CLR(NAME,VALUE) memset(NAME,VALUE,sizeof(NAME))

using namespace std;

int main() {
int n,i,k,a,b,c;
while( cin>>n,n ) {
   set<int> con;
   for(k=1;k<=n;k*=10) {
    a=(n/k)/11;

    //无进位
    b=(n/k) % 11;
    if( b<10 && (a!=0||b!=0) ) {
     c=n-a*11*k-b*k;
     if( c%2==0 ) {
      con.insert(a*k*10+b*k+c/2);
     }
    }

    //有进位
    b=(n/k) % 11-1;
    if( b>=0 && (a!=0||b!=0) ) {
     c=n-a*11*k-b*k;
     if( c%2==0 ) {
      con.insert(a*10*k+b*k+c/2);
     }
    }
   }

   if( con.size()==0 ) {
    printf("No solution. ");
    continue;
   }

   i=0;
   for(set<int>::iterator index=con.begin();index!=con.end();++index,++i) {
    printf("%d%c",*index,i==con.size()-1?' ':' ');
   }
}

     return 0;
}

Leftmost Digit(HDOJ 1060)

http://acm.hdu.edu.cn/showproblem.php?pid=1060

N^N=a*10^k //0<a<1,k为N^N的位数
两边取以10为底的对数
N*log10(N)=log10(a)+k
k=log10(N^N)=N*log10(N)取整
则log10(a)=N*log10(N)-取整(N*log10(N))

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

int MIN(int a,int b) { if( a<b ) return a; else return b; }
int MAX(int a,int b) { if( a>b ) return a; else return b; }
#define CLR(NAME,VALUE) memset(NAME,VALUE,sizeof(NAME))

using namespace std;

int main() {
int ca,n;
double x;
cin>>ca;
while( ca-- ) {
   cin>>n;
   x=n*log10((double)n);
   x=x-(__int64)x;
   cout<<(int)pow(10.0,x)<<endl;
}

     return 0;
}