SHARE
TWEET

Untitled

a guest Mar 16th, 2014 174 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define SYN ios_base::sync_with_stdio(0);cin.tie(0);
  3. using namespace std;
  4. /***************************************************************************************************************************************/
  5. typedef long long int LLI;
  6. typedef unsigned long long int ULLI;
  7. #define IMAX ((unsigned)1<<31)-1
  8. #define eps 1e-11
  9. #define LIMAX (1LL<<63)-1
  10. #define ULIMAX (1LL<<64)-1
  11. #define UIMAX ((LLI)1<<32)-1
  12. #define MP(X,Y) make_pair(X,Y)
  13.  
  14. #define REP(i,n) for(int i=0;i<n;i++)
  15. #define DREP(i,n) for(int i=n;i>=0;i--)
  16. #define LREP(i,a,b) for(int i=a;i<=b;i++)
  17. #define DLREP(i,a,b) for(int i=a;i>=b;i--)
  18. #define FOR(i,a,b,c) for(int i=a;i<=b;i+=c)
  19.  
  20. #define fill(a,v) memset(a,v,sizeof(a))
  21. #define DEBUG(x) cout << #x << ": " << x << endl;
  22. #define SZ(X) ((int)X.size())
  23. #define all(x) (x).begin(),(x).end()
  24. #define SORT(x) sort(all(x))
  25. #define VI vector<int>
  26. #define VS vector<string>
  27. #define PB push_back
  28. #define REV(a) reverse(all(a))
  29. typedef pair<int, int>PII;
  30. typedef pair<LLI, LLI>PLL;
  31. typedef pair<char, int>PCI;
  32. typedef pair<int, char>PIC;
  33. typedef pair<double, double>PDD;
  34. #define MSI map<string,int>
  35. #define MSLI map<string,LLI>
  36. #define MCI map<char,int>
  37. template<class T> inline T MIN_3(T a, T b, T c)
  38. {
  39.     return min(min(a, b), c);
  40. }
  41. template<class T> inline T MAX_3(T a, T b, T c)
  42. {
  43.     return max(max(a, b), c);
  44. }
  45. #define ACM(x) accumulate(all(x),0);
  46. #define CAP(x,y,z) set_intersection (all(x), all(y), z.begin())
  47. #define CUP(x,y,z) set_union(all(x),all(y),z.begin())
  48. #define DIF(x,y,z) set_difference (all(x),all(y),z.begin());
  49. #define BRPS(n,bit) bitset<bit>(n)
  50. #define DSORT(X)  sort(X.rbegin(), X.rend());
  51. #define read(x) freopen(#x".txt","r",stdin)
  52. #define write(x) freopen(#x".txt","w",stdout)
  53. #define LB(A, x) (lower_bound(all(A), x) - A.begin())//exactly where it starts
  54. #define UB(A, x) (upper_bound(all(A), x) - A.begin())
  55. #define UNQ(x) SORT(x),(x).erase(unique(all(x)),x.end())
  56.  
  57. template<class T> inline T BIGMOD(T n, T m, T mod)
  58. {
  59.     LLI ans = 1;
  60.     LLI k = n;
  61.     while(m)
  62.     {
  63.         if(m & 1)
  64.         {
  65.             ans *= k;
  66.             if(ans>mod) ans %= mod;
  67.         }
  68.         k *= k;
  69.         if(k>mod) k %= mod;
  70.         m >>= 1;
  71.     }
  72.     return ans;
  73. }
  74.  
  75.  
  76. inline int DBLCMP(double a, double b)
  77. {
  78.     if(fabs(a - b) <= eps) return 0;
  79.     if(a < b) return -1;
  80.     return 1;
  81. }
  82. template<class T> inline T sqr(T x)
  83. {
  84.     return x*x;
  85. }
  86. template<class T> inline int countbit(T n)
  87. {
  88.     return (n == 0) ? 0 : (1 + countbit(n&(n - 1)));
  89. }
  90. template<class T> inline T euclide(T a, T b, T &x, T &y)
  91. {
  92.     if (a < 0)
  93.     {
  94.         T d = euclide(-a, b, x, y);
  95.         x = -x;
  96.         return d;
  97.     }
  98.     if (b < 0)
  99.     {
  100.         T d = euclide(a, -b, x, y);
  101.         y = -y;
  102.         return d;
  103.     }
  104.     if (b == 0)
  105.     {
  106.         x = 1;
  107.         y = 0;
  108.         return a;
  109.     }
  110.     else
  111.     {
  112.         T d = euclide(b, a % b, x, y);
  113.         T t = x;
  114.         x = y;
  115.         y = t - (a / b) * y;
  116.         return d;
  117.     }
  118. }
  119. template<class T> string toString(T n)
  120. {
  121.     ostringstream ost;
  122.     ost << n;
  123.     ost.flush();
  124.     return ost.str();
  125. }
  126. template<class T> string toBinary(T n)
  127. {
  128.     string ret="";
  129.     while(n)
  130.     {
  131.         if(n%2==1)ret+='1';
  132.         else ret+='0';
  133.         n>>=1;
  134.     }
  135.     reverse(ret.begin(),ret.end());
  136.     return ret;
  137. }
  138. void combination(int n,vector< vector<int> > &ret)
  139. {
  140.     ret.resize(n+1, vector<int>(n+1, 0));
  141.     for(int i=1; i<=n; i++)
  142.     {
  143.         ret[i][0]=ret[i][i]=1;
  144.         for(int j=1; j<i; j++)
  145.         {
  146.             ret[i][j]=ret[i-1][j]+ret[i-1][j-1];
  147.         }
  148.     }
  149. }
  150. int toInt(string s)
  151. {
  152.     int r = 0;
  153.     istringstream sin(s);
  154.     sin >> r;
  155.     return r;
  156. }
  157. LLI toLInt(string s)
  158. {
  159.     LLI r = 0;
  160.     istringstream sin(s);
  161.     sin >> r;
  162.     return r;
  163. }
  164. double toDouble(string s)
  165. {
  166.     double r = 0;
  167.     istringstream sin(s);
  168.     sin >> r;
  169.     return r;
  170. }
  171. vector<string> parse(string temp)
  172. {
  173.     vector<string> ans;
  174.     ans.clear();
  175.     string s;
  176.     istringstream iss(temp);
  177.     while (iss >> s)ans.PB(s);
  178.     return ans;
  179. }
  180. template<class T> inline T gcd(T a, T b)
  181. {
  182.     if (a < 0)return gcd(-a, b);
  183.     if (b < 0)return gcd(a, -b);
  184.     return (b == 0) ? a : gcd(b, a % b);
  185. }
  186. template<class T> inline T lcm(T a, T b)
  187. {
  188.     if (a < 0)return lcm(-a, b);
  189.     if (b < 0)return lcm(a, -b);
  190.     return a*(b / gcd(a, b));
  191. }
  192. template<class T> inline T power(T b, T p)
  193. {
  194.     if (p < 0)return -1;
  195.     if (b <= 0)return -2;
  196.     if (!p)return 1;
  197.     return b*power(b, p - 1);
  198. }
  199. #define fst first
  200. #define snd second
  201. //istringstream(temp) >> data >> value >> stamp;
  202. //mod1 = 1000000007, mod2 = 1000000009;
  203. //.016-.040-.900-2.48
  204. /***************************************************************************************************************************************/
  205. #define sqr 320
  206. #define Mx (317*317)
  207. bool chk[Mx];
  208. VI primes;
  209.  
  210. void sieve()
  211. {
  212.     for(int i=2; i<=sqr; i++)
  213.     {
  214.         if(!chk[i])
  215.         {
  216.             for(int j=i+i; j<Mx; j+=i)
  217.             {
  218.                 chk[j]=true;
  219.             }
  220.         }
  221.     }
  222.     primes.PB(2);
  223.     for(int i=3;i<Mx;i+=2)if(!chk[i])primes.PB(i);
  224. }
  225. int N,K;
  226. VI V;
  227. int mem[5111];
  228. int psz;
  229.  
  230. map<int,bool>bad;
  231. int fu(int N)
  232. {
  233.     int ct=0;
  234.     int ret=0;
  235.     //int mid=sqrt(N);
  236.     REP(i,psz)
  237.     {
  238.         //if(primes[i]>mid)break;
  239.         ct=0;
  240.         while(N%primes[i]==0)
  241.         {
  242.             N/=primes[i];
  243.             ct++;
  244.         }
  245.         if(ct)
  246.         {
  247.             if(bad.find(primes[i])==bad.end())
  248.             {
  249.                 ret+=ct;
  250.             }
  251.             else
  252.             {
  253.                 ret-=ct;
  254.             }
  255.             //mid=sqrt(N);
  256.         }
  257.         if(N==1)break;
  258.     }
  259.     if(N!=1)
  260.     {
  261.         if(bad.find(N)==bad.end())ret++;
  262.         else ret--;
  263.     }
  264.     return ret;
  265. }
  266. int benifit(int n)
  267. {
  268.     if(n==1)return 0;
  269.     return fu(n);
  270. }
  271. VI Div;
  272. int sum[5111];
  273. int main()
  274. {
  275.     sieve();
  276.     psz=primes.size();
  277.     scanf("%d %d",&N,&K);
  278.     V.resize(N);
  279.     int x;
  280.     REP(i,N)scanf("%d",&V[i]);
  281.     REP(i,K){scanf("%d",&x);bad[x]=true;}
  282.     int g=V[0];
  283.     for(int i=0;i<N;i++)
  284.     {
  285.         g=gcd(g,V[i]);
  286.         Div.PB(g);
  287.     }
  288.     int uu=0;
  289.     REP(i,N)
  290.     {
  291.         uu+=fu(V[i]);
  292.     }
  293.     int res=0;
  294. //    for(int i=N;i>0;--i){
  295. //
  296. //        x = V[0];
  297. //
  298. //        for(int j=0;j<i;++j)
  299. //            x = gcd(x,V[j]);
  300. //
  301. //        if(benifit(x) < 0){
  302. //            for(int j=0;j<i;++j)
  303. //                V[j] /= x;
  304. //        }
  305. //    }
  306.     for(int i=Div.size()-1;i>=0;i--)
  307.     {
  308.         //cout << "# " << div[i] << benifit(div[i]) << endl;
  309.         int ben=benifit(Div[i]);
  310.         if(ben<0)
  311.         {
  312.             for(int j=i;j>=0;j--)
  313.             {
  314.                 V[j]/=gcd(V[j],Div[i]);//******************************.........................
  315.                 Div[j]/=gcd(Div[j],Div[i]);//****************************.......................
  316.             }
  317.         }
  318.     }
  319.     res=0;
  320.     REP(i,N)res+=fu(V[i]);
  321.     //cout << uu << " : " << max(res,uu) << endl;
  322.     cout << max(res,uu) << endl;
  323.     return 0;
  324. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top