15 solutions

  • 3
    @ 2022-1-6 20:43:25

    首先给出的数如果是素数那么就不能拆成两个数相乘那么此时的x就只能为该数本身,若不是素数那么拆成的两个数还需判断是否能整除

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	long long n;
    	cin>>n;
    	if(n<=3) cout<<n;
    	else{
    		long long l=0x3f3f3f3f3f3f;
    		int ox=0;
    		for(long long c=2;c*c<=n;c++){
    			if(n%c==0){
    				long long k=n/c;
    				if(k%c==0){
    					ox=1;
    					long long p=k/c;
    					l=min(l,p);
    				}
    			}
    		}
    	if(ox) cout<<l;
    	else cout<<n;
    	}
    	return 0;
    }
    
    • 1
      @ 2022-4-4 13:54:00

      一个平方数的质因子的幂次是偶数 所以只需要在n中找到质因子的幂次是奇数的就可以了

      #include <iostream>
      #include <cstring>
      #include <algorithm>
      
      using namespace std;
      
      int main() {
          long long n; cin >> n;
      
          for (long long i = 2; i <= n / i; i ++ ) {
              while (n % (i * i) == 0) n /= (i * i);
          }
      
          cout << n << endl;
      }
      
      • 1
        @ 2022-1-18 12:26:05

        首先我们知道一个正整数可以拆成n个质数积,若存在一个数x与n相乘使其变为完全平方数,要求x,我们只需将n分解出的质数中奇数个的质数乘进x即可,下面是代码,应该算暴力 ,不知道有没有更合理的做法

        #include<iostream>
        #include<cmath>
        using namespace std;
        //质数判断
        bool j(int x){
        	if(x==2||x==3)return true;
        	if(x==4)return false;
        	for(int i=2;i<4/i;i++)
        		if(x%i==0)return false;
        	return true;
        }
        
        long long int n,x=1;
        
        int main(){
        	scanf("%lld",&n);
        	if(n==2)printf("2");
        	else{
        		for(long long int i=2;i<=n;i++){
        			long long int k=0;
                    //判断该数是否为质数,如果是,n中含有几个
        			while(n%i==0&&j(i)){
        				n/=i;
        				k++;
        			}
        			if(k%2==1)x*=i;//奇数个则需乘进x
        		}
        		printf("%lld",x);
        	}
        	return 0;
        }
        
        • 1
          @ 2022-1-17 22:51:54

          题目来源

          2021年蓝桥省赛第二场H题

          题目链接:http://acm.mangata.ltd/p/P1165

          视频讲解

          https://www.bilibili.com/video/BV1aZ4y1f76j

          思路

          我们来考虑n的情况

          • 当n为质数的时候:我们直接返回当前这个数即可
          • 当n不是质数的时候:由于我们之前学过的唯一分解定理(学习链接:https://blog.csdn.net/m0_46201544/article/details/122280910 )可以知道一个合数是会被一种最小质数的积的形式的,那么我们只需要判断在这个过程中每一个质数的数量即可,我们只需要给奇数个质数因子再乘上一个该质数就可以让这个数变成完全平方数,所以我们直接使用唯一分解定理求解就好啦

          代码

          #include<bits/stdc++.h>
          using namespace std;
          #define ll long long
          #define mod 1000000009
          ll ksm(ll a,ll b) {
          	ll ans = 1;
          	for(;b;b>>=1LL) {
          		if(b & 1) ans = ans * a % mod;
          		a = a * a % mod;
          	}
          	return ans;
          }
          
          ll lowbit(ll x){return -x & x;}
          
          const int N = 2e6+10;
          
          ll n;
          
          int main()
          {
          	cin>>n;
          	ll ans = 1;
          	for(ll i = 2;i * i <= n; ++i) {
          		ll cnt = 0;
          		while(n % i == 0) {
          			cnt++;
          			n/=i;
          		}
          		if(cnt & 1) ans *= i;
          	}
          	ans *= n;
          	cout<<ans<<endl;
          	return 0;
          }
          
          • 0
            @ 2023-8-22 22:31:44

            打卡喵

            from math import *
            
            n = int(input())
            i = 2
            while i <= n / i:
                while n % (i * i) == 0:
                    n /= i * i
                i += 1
            
            print(int(n))
            
            • 0
              @ 2022-7-4 13:03:41

              #include <bits/stdc++.h> using namespace std; #define ll long long int main() { ll n,res=1; cin>>n; for(ll i=2;i<=n;i++) { ll gcc=0; while(n%i0) { n/=i; gcc++; } if(gcc%21)res*=i; } cout<<res; return 0; }

              • 0
                @ 2022-1-19 17:29:20

                签到

                #include<stdio.h>
                #include<math.h>
                #include<bits/stdc++.h>
                using namespace std;
                #define ll long long
                
                int main()
                {
                	ll n;
                	cin>>n;
                	ll ans = 1;
                	for(int i = 2; i *i <= n; ++ i)
                	{
                		ll end = 0;
                		while(n % i == 0)
                		{
                			end ++;
                			n /= i;
                		}
                		if(end & 1)ans *= i;
                	}
                	ans *= n;
                	cout<<ans<<endl;
                  return 0;
                }
                
                • 0
                  @ 2022-1-19 10:06:22
                  #include<bits/stdc++.h>
                  #define ll long long 
                  using namespace std;
                  int main()
                  {
                  	ll n;
                  	ll qwq=1;
                  	cin>>n;
                  	for(int i=2;i*i<=n;i++)
                  	{
                  		int num=0;
                  		while(n%i==0)
                  		{
                  			n/=i;
                  			num++;
                  		}
                  		if(num%2!=0)
                  		qwq*=i;
                  	}
                  	cout<<qwq*n;
                  	return 0;
                  }
                  
                  • 0
                    @ 2022-1-18 22:10:27
                    #include<iostream>
                    #include<algorithm>
                    #include<cstring>
                    #include<cmath>
                    #include<vector>
                    #include<map>
                    using namespace std;
                    typedef long long ll; 
                    int main(){
                    	ios::sync_with_stdio(false);
                    	ll x,ans=1;
                    	cin>>x;
                    	for(int i=2;i<=x/i;i++){
                    		int cou=0;
                    		while(x%i==0){
                    			x/=i;
                    			cou++;
                    		}
                    		if(cou&1)ans*=i;
                    	}
                    	if(x>1)ans*=x;
                    	cout<<ans;
                    
                    	return 0;
                    }
                    
                    • 0
                      @ 2022-1-18 17:12:02

                      打卡

                      #include<bits/stdc++.h>
                      using namespace std;
                      typedef long long ll;
                      ll n,fg,ans=1;
                      int main()
                      {
                      	cin>>n;
                      	for(ll i=2;i*i<=n;++i)
                      	{
                      		fg=0;
                      		while(n%i==0)
                      		{
                      			fg++;
                      			n/=i;
                      		}
                      		if(fg%2!=0) ans*=i;
                      	}
                      	ans*=n;
                      	cout<<ans<<"\n";
                      	
                      	return 0;
                       } 
                      
                      • 0
                        @ 2022-1-18 16:49:33
                        #include<bits/stdc++.h>
                        using namespace std;
                        int main(){
                        	long long n;
                        	cin>>n;
                        	long long ans=1;
                        	for(long long i=2;i<=n;i++){
                        		int num=0;
                        		while(n%i==0){
                        			n=n/i;
                        			num++;
                        			
                        		}
                        		if(num%2!=0){
                        			ans=ans*i;
                        		}
                        	}
                        	cout<<ans;
                        	return 0;
                        }
                        
                        • 0
                          @ 2022-1-18 15:50:20

                          #打卡

                          #include<iostream>
                          #include<algorithm>
                          #include<cstring>
                          #include<cmath>
                          #include<vector>
                          #include<map>
                          #include<stack>
                          #define ll long long
                          using namespace std;
                          int main(){
                          	ios::sync_with_stdio(false);
                          	ll n,an,ans=1;
                          	cin>>n;
                          	for(int i=2;i*i<=n;i++){
                          		an=0;
                          		while(n%i==0){
                          			an++;
                          			n=n/i;
                          		}
                          		if(an%2!=0) ans*=i;
                          	}
                          	ans*=n;
                          	cout<<ans<<endl;
                          	return 0;
                          }
                          
                          • 0
                            @ 2022-1-18 14:47:47

                            打卡

                            #include <bits/stdc++.h>
                            using namespace std;
                            int main(){
                            	long long n,ans=1;
                            	scanf("%lld",&n);
                            	for(int i=2;i*i<=n;i++){
                            		int sum=0;
                            		while(n%i==0){
                            			sum++;
                            			n/=i;
                            		}
                            		if(sum&1){
                            			ans*=i;
                            		}
                            	}
                            	cout<<ans*n;
                            	return 0;
                            }
                            • 0
                              @ 2022-1-18 14:12:42

                              #打卡

                              #include <bits/stdc++.h>
                              typedef long long ll;
                              using namespace std;
                              ll isprime(ll x)
                              {
                              	int ret=1;
                              	if(x==2) ret=1;
                              	if(x==1||x==0) ret=0;
                              	for(ll i=2;i<=sqrt(x);i++)
                              	{
                              		if(x%i==0)
                              			ret=0;
                              	}
                              	return ret;
                              }
                              int main()
                              {	ll n;
                              	cin>>n;
                              	if(isprime(n)) 
                              	{
                              		cout<<n<<endl;
                              		return 0;
                              	}
                              	ll ans=1;
                              	for(ll i=2;i*i<=n;i++)
                              	{
                              		ll cnt=0;
                              		while(n%i==0)
                              		{
                              			cnt++;
                              			n/=i;
                              		}
                              		if(cnt&1) ans*=i;
                              	}
                              	ans*=n;
                              	cout<<ans<<endl;
                              	return 0;
                              }
                              
                              • 0
                                @ 2022-1-18 11:42:15

                                运用了一个位运算异或来判断分解的奇偶,本人代码写的判断素数和分解有点重复;

                                #include<bits/stdc++.h>
                                using namespace std;
                                typedef long long ll;
                                const int N =1e6+5;
                                int check(ll x)
                                {
                                	if(x==1) return 0;
                                	int i;
                                	for(i=2;i*i<=x;i++)
                                	{
                                		if(x%i==0) break;
                                	}
                                	if(i*i>x) return 1;
                                	return 0;
                                }
                                int main()
                                {
                                	ll n,pp=1;
                                	cin>>n;
                                	if(check(n)) cout<<n<<endl;
                                	else{
                                		for(int i=2;i*i<n;i++)
                                		{
                                			ll a=0;
                                			while(n%i==0)
                                			{
                                				a^=i;
                                				n/=i;
                                			}
                                			if(a) pp*=a;
                                
                                			if(check(n))
                                			{
                                				pp*=n;
                                				break;
                                			}
                                		}
                                		cout<<pp<<endl;
                                	}	
                                	return 0;
                                }
                                
                                • 1

                                Information

                                ID
                                189
                                Time
                                1000ms
                                Memory
                                256MiB
                                Difficulty
                                8
                                Tags
                                # Submissions
                                520
                                Accepted
                                97
                                Uploaded By