pastebin

Paste Search Dynamic
Recent pastes
sieve
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int size=1e6;
  5. int t,n,snt[size],d[size];
  6. void sieve() {
  7.         snt[1]=1;
  8.         for (int i=2; i*i<=size; ++i) {
  9.        if (snt[i]==0) {
  10.            for (int j=i*i; j<=size; j+=i) {
  11.                if (snt[j]==0) {
  12.                     snt[j]=i;
  13.                 }
  14.             }
  15.         }
  16.     }
  17.     for (int i=2; i<=size; ++i) {
  18.         if (snt[i]==0) {
  19.             snt[i]=i;
  20.         }
  21.     }
  22. }
  23. int solve(int n) {
  24.         if (d[n]!=0) {
  25.                 return d[n];
  26.         }
  27.         int S=1;
  28.         while (n>1) {
  29.                 int tmp=snt[n],sl=0;
  30.                 while (n%tmp==0) {
  31.                         n/=tmp;
  32.                         sl++;
  33.                 }
  34.                 cout<<tmp<<" "<<sl<<endl;
  35.             if (sl%2==1) {
  36.              S*=tmp;
  37.             }
  38.  
  39.         }
  40.         return d[n]=S;
  41. }
  42. signed main() {
  43.         sieve();
  44.     cin>>t;
  45.     while (t--) {
  46.         cin>>n;
  47.         cout<<solve(n)<<endl;
  48.     }
  49. }
Parsed in 0.006 seconds