首页 > 代码库 > uva 10375

uva 10375

  1  /*  选择与除法_________________________________________________________________________________
  2                         
  3                           #include <iostream> 
  4                           #include <map> 
  5                           #include <cmath>
  6                           #include <vector>
  7                           #include <cstdio>
  8                           #include <string>
  9                           #include <cstring> 
 10                           #include <algorithm>    
 11                           using namespace std; 
 12                           #define fir first
 13                           #define sec second
 14                           #define pb(x) push_back(x) 
 15                           #define mem(A, X) memset(A, X, sizeof A)
 16                           #define REP(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
 17                           #define rep(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i)) 
 18                           #define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e) 
 19                           typedef long long LL;   
 20                           typedef unsigned long long ull;
 21                           typedef pair<long,long>  pll;     
 22                           
 23                           
 24                           LL T,n;
 25                           const int mod=1e9+7; 
 26                           const int maxn=10000;    
 27                           int num[maxn+1];
 28 const int SIZE=1e5+300;//1e6;   
 29                             bool isprime[SIZE];// filter[i]=true 表示i是素数.  筛选的范围是  0,1,2,... SIZE-1.  共SIZE个.    如果想筛0到7的素数,就把SIZE定为7+1;(因为总是多了个0)
 30                             void primefilte()  
 31                             {  
 32 
 33                               for(int i=0;i<=1;i++) isprime[i]=false;
 34                               for (int i=2; i<=SIZE; i++)
 35                                {
 36                                 if(i & 1 || i==2) isprime[i] = true;
 37                                 else isprime[i] = false;
 38                               }
 39 
 40                               for (int i=3; i<=(int)sqrt((long double)SIZE); i++)  
 41                               {  
 42                                 if (isprime[i])  
 43                                 {  
 44                                   int j = i*2;  
 45                                   while (j<=SIZE)  
 46                                   {  
 47                                     if (isprime[j])  
 48                                       isprime[j] = false;  
 49                                     j+=i;  
 50                                   }  
 51                                 }  
 52                               }  
 53                                                                                           //for (int i=2; i<=SIZE-1; i++)  
 54                                                                                            // if (isprime[i]) printf("%d ",i);  
 55                             } 
 56 
 57                           vector<int> base;
 58                           void addint(int n,int p)
 59                           {
 60                               REP(i,0,base.size()-1)
 61                               {
 62                                   while(n%base[i]==0) 
 63                                       {
 64                                           num[i]+=p; 
 65                                           n/=base[i];
 66                                       }
 67                               }
 68                           }
 69                           void addf(int n,int p)
 70                           {
 71                               //rep(i,n,2)
 72                                //num[i]+=p;
 73                               REP(i,2,n)
 74                               addint(i,p);
 75                           }
 76                           int main()
 77                           {
 78                                freopen("in.txt","r",stdin); 
 79                                //while(cin>>n)
 80 
 81                                primefilte();
 82                                REP(i,2,10000)
 83                                if(isprime[i]) base.pb(i);
 84 
 85                                int p,q,r,s;
 86                                while(cin>>p>>q>>r>>s)
 87                                { 
 88                                  //REP(kase,1,T)  { }
 89                                  mem(num,0);
 90                                  addf(p,1);
 91                                  addf(s,1);              
 92                                  addf(r-s,1);              
 93                                  addf(p-q,-1);     
 94                                  addf(q,-1);     
 95                                  addf(r,-1);
 96                                  double ans=1;
 97                                  REP(i,0,base.size()-1)
 98                                   ans*=pow(base[i],num[i]);              
 99                                  printf("%.5lf\n",ans);
100                                }
101                             return 0;
102                           }
103               
104                          /*
105                             note    :  有一个地方:刚开始直接用的1 2 3 ... 10000作的基(写起来简单),出错了,
106                                         因为这样表示太浪费,损失了精度(几乎每次计算都是很小的数计算,误差增大),
107                                         于是希望稠密表示,减少误差,唯一分解定理(单次计算数字增大),使得误差降低.
108                             debug   :  代码除了模板其他的代码不要复制,不然易出错.应该重新写
109                             optimize:
110                           */ 

 

uva 10375