送分给会数据结构的朋友

P是一个由基本元素a,b生成的仅含有非负整数的集合，a,b∈P，P 中其它元素可由下述规则生成:
    对任意的x∈P，任意的Y∈P，必有│xy-x-y│∈P。
    P中其它元素可由基本元素a,b及上述规则唯一确定。
    编程对输入的a,b,c,判断c是否属于P。
    对a,b,c请采用longint型,a,b,c<10^9。

11 个解决方案

#1

大家想想,我要结帖了

#2

P是一个群。。。

然后用群的性质来解这道题

#3

我觉得仅根据那两条规则，还不能确定集合P.

#4

群倒是一个蛮不错的酸法

#5

p由x,y生成，则对任意一个a∈P,有a=((1-x)**i)((1-y)**j)-1。
(1-x)**i表示（1-x)的i次幂。
判断：1，a=a-1;
      2,循环a=a/(1-x)直到，a不能被（1-x)整除为止；
      3，循环a=a/(1-y)直到，a不能被（1-y)整除为止；
      4，如果a这是不为0，则a不属于p；否则属于p。

#6

抱歉，1，a=a+1;
p由x,y生成，则对任意一个a∈P,有a=((1-x)**i)((1-y)**j)-1。
(1-x)**i表示（1-x)的i次幂。
判断：1，a=a+1;
      2,循环a=a/(1-x)直到，a不能被（1-x)整除为止；
      3，循环a=a/(1-y)直到，a不能被（1-y)整除为止；
      4，如果a这是不为0，则a不属于p；否则属于p。

#7

题目答案:
http://210.28.172.18/jyjx/noi/problem/pc953.htm

#8

感觉没有好的方法，穷举一把，对于大的数据，速度和内存开销肯能会成为一个问题。

#include <stdio.h>
#include <math.h>
#include <set>
using namespace std;

set<int> s;
int main()
{
   int a,b,c;
   scanf("%d%d%d",&a,&b,&c);
   s.insert(a);
   s.insert(b);
   if(a==2||b==2){
      if(b==2){
  b==a;a==2;
      }
      int u=b-2;
      while(u>=0){if(u<=c)s.insert(u);u-=2;}
   }

   set<int>::iterator it;
   for(it=s.begin();it!=s.end();++it){
      int x=*it;
      if(x==c){
      printf("True\n");
      return 0;
      }
      set<int>::iterator it2;
      for(it2=s.begin();it2!=it;++it2){
int y=*it2;
int z=abs(x*y-x-y);
if(z<=c)
    s.insert(z);
if(z==c){
            printf("True\n");
    return 0;
}
      }
   }
   printf("False\n");
   return -1;
}

#9

对于包含0，1，2可以特殊处理。
主要是处理只包含>=3的数字的情况，
比如对于
3 5 100000001
需要550M的内存

#10

标识

#11

#include <stdio.h>
#include <math.h>
#include <set>
using namespace std;

set<int> s;
int limit;

int hit(int c){
   int lim=(int)sqrt(c+1);
   int i;
   if(c<limit||c<=3) return s.find(c)!=s.end();
   if(s.find(c)!=s.end())return true;
   for(i=2;i<=lim;i++){
      if((c+1)%i==0){
         if(hit(i+1)&&hit((c+1)/i+1))return true;
      }
   }
   return false;
}

int main()
{
   int a,b,c;
   scanf("%d%d%d",&a,&b,&c);
   s.insert(a);
   s.insert(b);
   limit=(int)sqrt(c);
   if(a==2||b==2){
      if(b==2){
  b==a;
      }
      if(b>3){
  if(((c-b)&1)&&(c!=2)){
     printf("False\n");
     return -1;
  }else{
     printf("True\n");
     return 0;
  }
      }
   }

   set<int>::iterator it;
   for(it=s.begin();it!=s.end();++it){
      int x=*it;
      set<int>::iterator it2;
      for(it2=s.begin();it2!=it;++it2){
int y=*it2;
long long z=abs((long long)x*y-x-y);
if(z<limit)
    s.insert((int)z);
         else break;
      }
   }
   if(hit(c)){printf("True\n");return 0;}
   printf("False\n");
   return -1;
}

#1