E1. Square-free division (easy version) (数论、思维)

末蓝、 2021-07-16 15:21 367阅读 0赞

[题目][Link 1]

思路：首先贪心的想一想，我让每一段尽可能长，则最后的段数就可能越少。

再来看什么时候一个数是平方数，将一个数质因数分解  
X=a^x1 \* b^x2 \* c^x3…  
只要让一个数的x1 x2 x3…xn都为偶数即可  
那我们只需发现如果有相乘的两个数各自的质因数次方相加全为偶数则会组成一个平方数，就需要切出一段来。但这个记录各自质因数再让每个相加又太麻烦，所以就想出了一个简便的记录方法，只要记录质因数次数为奇数的所有质因数乘积（把为偶数的部分扔掉，偶数部分不会影响判断），如果发现有两个这种乘积相等，则此段出现质因数，细节见代码。

Code:

#include<iostream>
    #include<map>
    using namespace std;
    
    int divid(int n)
    { 
    	if (n == 1)return 1;
    	int ans = 1;
    	for(int i=2;i*i<=n;i++)
    	{ 
    		int sum = 0;
    		if (n % i == 0)
    		{ 
    			while (n % i == 0)
    			{ 
    				sum++;
    				n /= i;
    			}
    		}
    		if (sum % 2 == 1)ans *= i;
    	}
    	ans *= n;
    	return ans;
    }
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, k;cin >> n >> k;
    		map<int, int> ma;
    		int ans = 0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			int v;cin >> v;
    			int p = divid(v);
    			if (ma[p])
    			{ 
    				ans++;
    				ma.clear();
    			}
    			ma[p]++;
    		}
    		cout << ans+1 << endl;
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1497/E1

发表评论取消回复

表情：

评论列表（有 0 条评论，367人围观）

还没有评论，来说两句吧...

相关阅读

相关 atcoder abc158 E - Divisible Substring

atcoder abc158 E - Divisible Substring 先看题面 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5n

╰+哭是因爲堅強的太久メ/ 2023年07月12日 11:54/ 0 赞/ 5 阅读

相关 Codeforces Round #661 (Div. 3) E1. Weights Division (easy version) 题解 dfs树的遍历+贪心+优先队列

[原题链接：E1. Weights Division (easy version)][E1. Weights Division _easy version] 题目描述

绝地灬酷狼/ 2022年11月25日 11:43/ 0 赞/ 110 阅读

相关 C. Strange Function (思维+数论)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCN5a2X5LiN6

墨蓝/ 2022年09月13日 06:19/ 0 赞/ 185 阅读

相关 Palindromes _easy version

Palindromes \_easy version Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目

约定不等于承诺〃/ 2022年08月10日 04:55/ 0 赞/ 139 阅读

相关 Tiling_easy version——找规律

Tiling\_easy version Problem Description 有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格

深藏阁楼爱情的钟/ 2022年06月06日 09:05/ 0 赞/ 226 阅读

相关 Tiling_easy version

> Description > > 有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设的方法。

左手的ㄟ右手/ 2022年04月17日 00:26/ 0 赞/ 180 阅读

相关 E1. Close Tuples (easy version)

[题目][Link 1] 原谅兄弟我只A了easy…所以就写个easy的题解吧… 思路：用一个map记录各个值的次数，然后如果某数字数量>=3则可以构成n\(n-1

矫情吗；*/ 2021年07月16日 22:03/ 0 赞/ 274 阅读

相关 C - k-LCM (easy version AND hard version) (构造、思维)

[题目][Link 1] 思路：先来考虑k=3的情况，如果n为奇数则三个数分别为 1 n/2 n/2，这样最大是n/2。如果n为偶数，如果n%4==0，则三个数为 n/

àì夳堔傛蜴生んèń/ 2021年07月16日 21:10/ 0 赞/ 340 阅读

相关 1469D - Ceil Divisions （思维）

[题目][Link 1] 思路：首先对于1 2 3 4 . . . 2e5 我想啊，让 i=3 到 2e5-1的数全部 i/2e5 那么这些数就全为1了，1 2 1 1

淩亂°似流年/ 2021年07月16日 16:32/ 0 赞/ 265 阅读

相关 E1. Square-free division (easy version) (数论、思维)

[题目][Link 1] 思路：首先贪心的想一想，我让每一段尽可能长，则最后的段数就可能越少。再来看什么时候一个数是平方数，将一个数质因数分解 X=a^x1

末蓝、/ 2021年07月16日 15:21/ 0 赞/ 368 阅读