14年安徽省赛数论题etc.

关于最大公约数的疑惑

题目描述

小光是个十分喜欢素数的人，有一天他在学习最大公约数的时候突然想到了一个问题，他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y)，即有多少(x,y),gcd(x,y)=素数，1<=x,y<=n。但是小光刚刚接触最大公约数，不能解决这个问题，于是他希望你能帮助他解决这个问题。

输入

多组测试数据，对于每组数据：

每行为一个整数N (1<=N<=10^5)

输出

对于每组数据：

每行输出 (x,y)的个数

样例输入

样例输出

直接筛法求素数+欧拉函数。在筛法求素数的时候顺便给每个数*（1-1/pi)其中pi为该数的质因子。

然后嘛这题有点坑他说的数对竟然是包括相同两个数的数对以及例如（2,4）及（4,2）这样顺序不同的数对算作两个数对。。。所以我刚打的时候好几遍都不能AC...

贴代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #define clr(x) memset(x,0,sizeof(x))

 using namespace std;

 int a[];

 int ct[];

 int pr[];

 void prime(int n);

 int main()

 {

     int n,m,i,j,sum;

     prime();

     while(scanf("%d",&n)==)

     {

         sum=;

         for(i=;pr[i]<=n;i++)

         {

             j=n/pr[i];

             sum+=ct[j];

         }

         printf("%d\n",sum*+i-);

     }

  }

 void prime(int n)

 {

     clr(a);

     clr(pr);

     int num=;

      a[]=a[]=;

      for(int i=;i<=n;i++)

        ct[i]=i;

     ct[]=;

      for(int i=;i<=n;i++)

      if(!a[i])

      {

          for(int j=i;j<=n;j+=i)

          {

              a[j]=;

              ct[j]=ct[j]/i*(i-);

          }

          pr[++num]=i;

      }

     for(int i=;i<=n;i++)

       ct[i]+=ct[i-];

     pr[]=num;

     return ;

 }

一道简单的几何变换

题目描述

小光最近在学习几何变换，老师给他留了一个作业，在二维平面上有n个点(x,y)，老师给了m个几何变换对n个点进行操作，要求小光输出变换后的n个点的坐标(x’,y’)。小光为了偷懒，请求你帮他写个程序来完成老师的作业。

由于小光刚刚学习几何变换，老师只会给出四种变换，如下：

平移变换： (x’,y’)=(x+p,y’+q) 程序的输入格式为：1 p q (p,q为整数)

缩放变换： (x’,y’)=(x*L,y*L) 程序的输入格式为：2 L (L为整数)

上下翻转： (x’,y’)=(x,-y) 程序的输入格式为：3

左右翻转： (x’,y’)=(-x,y) 程序的输入格式为：4

输入

多组测试数据，对于每组数据：

第一行为N(1<=N<=10^5)

然后以下N行，N个点(x,y) 其中x,y均为整数

然后一行为M (1<=M<=10^5)

然后以下M行，M个变换，输入格式如上所述。

输出

对于每组数据：

输出N行，每行为变换点坐标。

样例输入

2 1 1 2 2 1 1 1 1

样例输出

2 2 3 3

^{这题也没什么好说的。。其实算不上数论，只是顶着变换的名头= =。然后呢一看数据量如果分别一个一个处理一定会超时。于是就想到了把所有的处理化为一次处理。}

然后呢用ct 代表全部处理过后是否翻转变换 =1为没翻转，=-1为翻转了。两次翻转相当于没翻转。每次翻转后ct=-ct。

用l表示全部处理过后的缩放倍数。

然后平移变换和翻转以及缩放相关，处理比较麻烦，用acum存最后处理完平移的多少。每次平移变换为acum=+a*ct。每次缩放时acum=*t,t为每次缩放变换的大小

对于每个数a[i]处理完后为a[i].x=a[i].x*l*ctx+acumx*ctx; a[i].y=a[i].y*l*cty+acumy*cty;

代码处理如下：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 struct pos{

 int x,y;

 }a[];

 int main()

 {

 int ctx,cty,acumx,acumy;

 int n,m,k,l,t,p,q;

 while(scanf("%d",&n)==)

 {

 for(int i=;i<=n;i++)

 scanf("%d%d",&a[i].x,&a[i].y);

 scanf("%d",&m);

 ctx=cty=l=;

 acumx=acumy=;

 for(int i=;i<=m;i++)

 {

 scanf("%d",&k);

 if(k==)

 {

 scanf("%d%d",&p,&q);

 acumx+=ctx*p;

 acumy+=cty*q;

 }

 if(k==)

 {

 scanf("%d",&t);

 l*=t;

 acumx*=t;

 acumy*=t;

 }

 if(k==)

 cty=-cty;

 if(k==)

 ctx=-ctx;

 }

 for(int i=;i<=n;i++)

 {

 a[i].x=a[i].x*l*ctx+acumx*ctx;

 a[i].y=a[i].y*l*cty+acumy*cty;

 printf("%d %d\n",a[i].x,a[i].y);

 }

 }

 return ;

 }

巴特西

14年安徽省赛数论题etc.

关于最大公约数的疑惑

题目描述

输入

输出

样例输入

样例输出

一道简单的几何变换

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章