fork download
copy 
  1. ///  In the name of ALLAH
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef unsigned int uint;
  8. typedef unsigned long long ull;
  9.  
  10. #define PB push_back
  11. #define PF push_front
  12. #define FF first
  13. #define SS second
  14. #define MP make_pair
  15. #define endl '\n'
  16. #define all(a) (a).begin(),(a).end()
  17.  
  18. const double PI = acos(-1);
  19. const double eps = 1e-9;
  20. const int inf = 2000000000;
  21. const ll infLL = 9000000000000000000;
  22. #define MOD 1000000007
  23.  
  24. #define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25. #define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  26. #define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
  27. #define fix fixed<<setprecision(10)
  28.  
  29. int dx[]={1,-1,0,0,1,1,-1,-1};
  30. int dy[]={0,0,1,-1,1,-1,1,-1};
  31.  
  32. ll gcd(ll a,ll b) { return __gcd(a,b); }
  33. ll lcm(ll a,ll b) { return a*(b/__gcd(a,b)); }
  34.  
  35. /// Modular arithmetic
  36. inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
  37. inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
  38. inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
  39. inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
  40. inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
  41. inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
  42. inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
  43.  
  44. /// Policy Based Data Structure 
  45. /*
  46. #include <ext/pb_ds/assoc_container.hpp>
  47. #include <ext/pb_ds/tree_policy.hpp>
  48. #include <ext/pb_ds/detail/standard_policies.hpp>
  49. using namespace __gnu_pbds;
  50. typedef tree< ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set; 
  51. */
  52. /// find_by_order(x) find the number in  index x [ 0 based] and return an iterator at that index
  53. /// order_of_key(y) count the numbers that are strictly less than y
  54.  
  55.  
  56. /**************************************************************start**************************************************************/
  57.  
  58. const ll MX=1e8+123;
  59. bitset<MX>is_prime;
  60. vector<ll>prime,divisor_x;
  61.  
  62. void sieve(ll n){
  63.     n+=10;
  64.     for(ll i=3; i<=n; i+=2) is_prime[i]=1;
  65.     ll sq=sqrt(n);
  66.     for(ll i=3; i<=sq; i+=2){
  67.         if(is_prime[i]){
  68.             for(ll j=i*i; j<=n; j+=(i+i)){
  69.                 is_prime[j]=0;
  70.             }
  71.         }
  72.     }
  73.     is_prime[2]=1;
  74.     prime.PB(2);
  75.     for(ll i=3; i<=n; i+=2){
  76.         if(is_prime[i]){
  77.             prime.PB(i);
  78.         }
  79.     }
  80.     return;
  81. }
  82.  
  83. void divisor(ll n){
  84.     ll sq=sqrt(n);
  85.     for(ll i=1; i<=sq; i++){
  86.         if(n%i==0){
  87.             divisor_x.PB(i);
  88.             if(i!=(n/i)){
  89.                 divisor_x.PB(n/i);
  90.             }
  91.         }
  92.     }
  93.     return;
  94. }
  95.  
  96. ll sod(ll n){
  97.     ll ans=1LL;
  98.     for(auto it : prime){
  99.         if(it*it>n){
  100.             break;
  101.         }
  102.         if(n%it==0){
  103.             ll sum=1LL,mul=1LL;
  104.             while(n%it==0){
  105.                 n/=it;
  106.                 mul*=it;
  107.                 sum+=mul;
  108.             }
  109.             ans*=sum;
  110.         }       
  111.     }
  112.     if(n>1){
  113.         ans*=(1LL+n);
  114.     }
  115.     return ans;
  116. }
  117.  
  118. void Solution(void){
  119.  
  120.     ll n,x;
  121.     cin>>n>>x;
  122.  
  123.     ll lim=1e8;
  124.  
  125.     divisor(x);
  126.     map<ll,ll>mp;
  127.  
  128.     for(ll i=0; i<n; i++){
  129.         ll a;
  130.         cin>>a;
  131.         mp[(sod(a))]++;
  132.     }
  133.  
  134.     sort(all(divisor_x));
  135.  
  136.     ll ans=0;
  137.  
  138.     for(auto i : divisor_x){
  139.         for(auto j : mp){
  140.             ll value=i-j.first;
  141.             if(mp.find(value)!=mp.end()){
  142.                 auto it = mp.find(value);
  143.                 ll first = it->first;
  144.                 ll second = it->second;
  145.                 if(value==j.first){
  146.                     ans+=((second*(second-1LL)));
  147.                 }
  148.                 else{
  149.                     ans+=(1LL*second*(j.second));
  150.                 }
  151.             }
  152.         }
  153.     }
  154.  
  155.     cout<<(ans>>1LL)<<endl;
  156.     return;
  157. }
  158.  
  159.  
  160. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  161.  
  162.  
  163. int main(){
  164.  
  165.     optimize();
  166.  
  167. //    #ifndef ONLINE_JUDGE
  168. //        freopen("input.txt", "r", stdin);
  169. //        freopen("output.txt", "w", stdout);
  170. //        freopen("Error.txt", "w", stderr);
  171. //    #endif
  172.  
  173.     int testcase=1;
  174. //    cin>>testcase;
  175.  
  176.     for(int tc=1; tc<=testcase; tc++){
  177.         Solution();
  178.     }
  179.  
  180.     return 0;
  181. }
  182.  
  183. /// ALHAMDULILLAH
Success #stdin #stdout 0.01s 5664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/hW9RFO
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!